<p><a href="https://i.sstatic.net/YoHfs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YoHfs.png" alt="gadget" /></a></p>
<p>Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting.</p>
<p>Speckenmeyer proved that the undirected feedback vertex set problem is NP-hard on planar graphs with maximum degree of four. I try to adapt his gadgets to directed graphs. However, I cannot keep the planarity. But it satisfies the degree bounds.</p>
<p>We replace a vertex <span class="math-container">$x$</span> by this gadget and assign the entering arcs to <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>, and the leaving arcs to <span class="math-container">$d_1$</span> and <span class="math-container">$d_2$</span>. (It does not matter who receives two.)</p>
<p>In the gray box, there are four directed triangles. We need to remove at least two vertices to break them. The only choice is <span class="math-container">$\{b_1, b_2\}$</span>. This corresponds to a solution not containing <span class="math-container">$x$</span>. On the other hand, a solution containing <span class="math-container">$x$</span> can be replaced by <span class="math-container">$\{o, c_1, c_2\}$</span>.</p>

CC BY-SA 4.0
2023-03-03T08:33:27.903Z
After a second thought, I guess it's very unlikely the same approach can be applied to the planar case. The essential obstacle is that $K_{3,3}$ is not planar. We probably need a different source problem instead of degree reductions.
Yixin Cao
CC BY-SA 4.0
2023-03-06T04:43:18.807Z
Your construction of the gadget is much helpful. Perhaps, this problem would have been settled if my reduction for the planar version is correct.
Blanco
CC BY-SA 4.0
2023-03-03T08:20:29.020Z
2023-03-03T08:20:29.020Z
Yixin Cao
<p>Thanks to Prof. @Yixin Cao's construction of the reduction, I think I have found a way to show that Planar-DFVS remains <span class="math-container">$\textsf{NP}$</span>-hard when <span class="math-container">$(\Delta_{in}, \Delta_{out}) = (2, 2)$</span>.</p>
<p>We use the Vertex Cover in planar <span class="math-container">$3$</span>-regular Hamiltonian graphs to reduce.</p>
<p>Let <span class="math-container">$G$</span> be an instance of Vertex Cover in planar <span class="math-container">$3$</span>-regular Hamiltonian graphs.
<span class="math-container">$G$</span> is bridge-less, since <span class="math-container">$G$</span> is Hamiltonian.
According to <a href="https://en.wikipedia.org/wiki/Petersen%27s_theorem" rel="nofollow noreferrer">Peterson's theorem</a>, <span class="math-container">$G$</span> has a perfect matching, and let <span class="math-container">$M$</span> be a perfect matching of <span class="math-container">$G$</span>.</p>
<p><strong>STEP 1.</strong></p>
<p>For each edge <span class="math-container">$e$</span> in <span class="math-container">$G$</span>, we add a new <span class="math-container">$2$</span>-degree vertex <span class="math-container">$w_{e}$</span> connecting the endpoints of <span class="math-container">$e$</span>.</p>
<p>If <span class="math-container">$e$</span> is in <span class="math-container">$M$</span>, we orient the triangle containing <span class="math-container">$w_{e}$</span> in the anticlockwise direction; otherwise, we orient the triangle in the clockwise direction.</p>
<p>Let <span class="math-container">$x$</span> be a vertex in <span class="math-container">$G$</span>.
Without loss of generality, suppose there are one clockwise directed triangle and two anticlockwise directed triangles containing <span class="math-container">$x$</span>.</p>
<p><a href="https://i.sstatic.net/leGrk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/leGrk.png" alt="enter image description here" /></a></p>
<p>Now, the in-degree and out-degree of every vertex are exactly three.</p>
<p><strong>STEP 2.</strong></p>
<p>Based on Speckenmeyer's method, we use a gadget to replace each vertex <span class="math-container">$x$</span>.</p>
<p><a href="https://i.sstatic.net/y6hm8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/y6hm8.png" alt="enter image description here" /></a></p>
<p>As Prof. Cao's statements, in the dotted box, there are four directed triangles.
To Break all of them by using two vertices, we have a unique choice <span class="math-container">$\{u_{1},u_{5}\}$</span>.
This corresponds to a solution not containing <span class="math-container">$x$</span>.
On the other hand, a solution containing <span class="math-container">$x$</span> can always be replaced by <span class="math-container">$\{v_{1}, u_{3}, v_{3}\}$</span> or <span class="math-container">$\{v_{2}, u_{3}, v_{4}\}$</span>.</p>
<p>Therefore, we obtain a planar digraph with <span class="math-container">$(\Delta_{in}, \Delta_{out}) = (2, 2)$</span>.</p>

CC BY-SA 4.0
2023-03-04T00:32:49.263Z
What about a cycle entering from $u_1$ and leaving from $v_2$?
Yixin Cao
CC BY-SA 4.0
2023-03-03T20:07:03.640Z
2023-03-04T08:21:34.247Z
2023-03-04T08:21:34.247Z
Blanco
<p>My question is the directed version of this <a href="https://cstheory.stackexchange.com/questions/10901/is-the-feedback-vertex-set-problem-on-planar-bounded-degree-graphs-hard">one</a>. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback vertex set.)</p>
<p>In wiki, it says that <a href="http://en.wikipedia.org/wiki/Feedback_vertex_set" rel="nofollow noreferrer">directed Feedback vertex set (DFVS)</a> problem is <span class="math-container">$\mathsf{NP}$</span>-hard if the maximum in-degree <span class="math-container">$\Delta_{in} = 2$</span> and maximum out-degree <span class="math-container">$\Delta_{out} = 2$</span>; and planar directed Feedback vertex set problem is <span class="math-container">$\mathsf{NP}$</span>-hard if the maximum in-degree <span class="math-container">$\Delta_{in} = 3$</span> and maximum out-degree <span class="math-container">$\Delta_{out} = 3$</span>.</p>
<p>Here is what I know:</p>
<ol>
<li>When <span class="math-container">$(\Delta_{in}, \Delta_{out}) = (1, d)$</span>, DFVS is polynominal-time solvable.</li>
<li>When <span class="math-container">$(\Delta_{in}, \Delta_{out}) \geq (2, 2)$</span>, DFVS is <span class="math-container">$\mathsf{NP}$</span>-hard.</li>
<li>When <span class="math-container">$(\Delta_{in}, \Delta_{out}) \geq (3, 3)$</span>, Planar-DFVS is <span class="math-container">$\mathsf{NP}$</span>-hard.</li>
</ol>
<hr />
<ul>
<li>Item 1 is trivial I think.</li>
<li>Item 2 and 3 are claimed by <a href="https://en.wikipedia.org/wiki/Computers_and_Intractability" rel="nofollow noreferrer">Garey and Johnson's book</a>.</li>
<li>For Item 3, Vertex Cover in <span class="math-container">$3$</span>-degree planar graphs can reduce to Planar-DFVS with <span class="math-container">$(\Delta_{in}, \Delta_{out}) = (3, 3)$</span>.</li>
<li>I do not find the proof about item 2.</li>
<li>Is Planar-DFVS in <span class="math-container">$\mathsf{P}$</span> if <span class="math-container">$\Delta_{in}$</span> (or <span class="math-container">$\Delta_{out}$</span>) is no more than <span class="math-container">$2$</span>?</li>
</ul>

<cc.complexity-theory><reference-request><np-hardness><planar-graphs><bounded-degree>
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
Blanco
# NP-hardness: (planar) directed feedback vertex set problem with bounded degree

(Asked by: username_0 on 2023-03-03)

My question is the directed version of this [one](https://cstheory.stackexchange.com/questions/10901/is-the-feedback-vertex-set-problem-on-planar-bounded-degree-graphs-hard). (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback vertex set.)

In wiki, it says that [directed Feedback vertex set (DFVS)](http://en.wikipedia.org/wiki/Feedback_vertex_set) problem is $\mathsf{NP}$-hard if the maximum in-degree $\Delta\_{in} = 2$ and maximum out-degree $\Delta\_{out} = 2$; and planar directed Feedback vertex set problem is $\mathsf{NP}$-hard if the maximum in-degree $\Delta\_{in} = 3$ and maximum out-degree $\Delta\_{out} = 3$.

Here is what I know:

1. When $(\Delta\_{in}, \Delta\_{out}) = (1, d)$, DFVS is polynominal-time solvable.
2. When $(\Delta\_{in}, \Delta\_{out}) \geq (2, 2)$, DFVS is $\mathsf{NP}$-hard.
3. When $(\Delta\_{in}, \Delta\_{out}) \geq (3, 3)$, Planar-DFVS is $\mathsf{NP}$-hard.

---

* Item 1 is trivial I think.
* Item 2 and 3 are claimed by [Garey and Johnson's book](https://en.wikipedia.org/wiki/Computers_and_Intractability).
* For Item 3, Vertex Cover in $3$-degree planar graphs can reduce to Planar-DFVS with $(\Delta\_{in}, \Delta\_{out}) = (3, 3)$.
* I do not find the proof about item 2.
* Is Planar-DFVS in $\mathsf{P}$ if $\Delta\_{in}$ (or $\Delta\_{out}$) is no more than $2$?

**Tags:** cc.complexity-theory, reference-request, np-hardness, planar-graphs, bounded-degree


---

## 2 answers

### Answer by username_1 on 2023-03-03. Score: 1

[![gadget](https://i.sstatic.net/YoHfs.png)](https://i.sstatic.net/YoHfs.png)

Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting.

Speckenmeyer proved that the undirected feedback vertex set problem is NP-hard on planar graphs with maximum degree of four. I try to adapt his gadgets to directed graphs. However, I cannot keep the planarity. But it satisfies the degree bounds.

We replace a vertex $x$ by this gadget and assign the entering arcs to $a\_1$ and $a\_2$, and the leaving arcs to $d\_1$ and $d\_2$. (It does not matter who receives two.)

In the gray box, there are four directed triangles. We need to remove at least two vertices to break them. The only choice is $\{b\_1, b\_2\}$. This corresponds to a solution not containing $x$. On the other hand, a solution containing $x$ can be replaced by $\{o, c\_1, c\_2\}$.

> **Comments:**
> **username_1**: After a second thought, I guess it's very unlikely the same approach can be applied to the planar case. The essential obstacle is that $K_{3,3}$ is not planar. We probably need a different source problem instead of degree reductions.  
> **username_0**: Your construction of the gadget is much helpful. Perhaps, this problem would have been settled if my reduction for the planar version is correct.  

---

### Answer by username_0 on 2023-03-03. Score: 1

Thanks to Prof. @username_1's construction of the reduction, I think I have found a way to show that Planar-DFVS remains $\textsf{NP}$-hard when $(\Delta\_{in}, \Delta\_{out}) = (2, 2)$.

We use the Vertex Cover in planar $3$-regular Hamiltonian graphs to reduce.

Let $G$ be an instance of Vertex Cover in planar $3$-regular Hamiltonian graphs.
$G$ is bridge-less, since $G$ is Hamiltonian.
According to [Peterson's theorem](https://en.wikipedia.org/wiki/Petersen%27s_theorem), $G$ has a perfect matching, and let $M$ be a perfect matching of $G$.

**STEP 1.**

For each edge $e$ in $G$, we add a new $2$-degree vertex $w\_{e}$ connecting the endpoints of $e$.

If $e$ is in $M$, we orient the triangle containing $w\_{e}$ in the anticlockwise direction; otherwise, we orient the triangle in the clockwise direction.

Let $x$ be a vertex in $G$.
Without loss of generality, suppose there are one clockwise directed triangle and two anticlockwise directed triangles containing $x$.

[![enter image description here](https://i.sstatic.net/leGrk.png)](https://i.sstatic.net/leGrk.png)

Now, the in-degree and out-degree of every vertex are exactly three.

**STEP 2.**

Based on Speckenmeyer's method, we use a gadget to replace each vertex $x$.

[![enter image description here](https://i.sstatic.net/y6hm8.png)](https://i.sstatic.net/y6hm8.png)

As Prof. Cao's statements, in the dotted box, there are four directed triangles.
To Break all of them by using two vertices, we have a unique choice $\{u\_{1},u\_{5}\}$.
This corresponds to a solution not containing $x$.
On the other hand, a solution containing $x$ can always be replaced by $\{v\_{1}, u\_{3}, v\_{3}\}$ or $\{v\_{2}, u\_{3}, v\_{4}\}$.

Therefore, we obtain a planar digraph with $(\Delta\_{in}, \Delta\_{out}) = (2, 2)$.

> **Comments:**
> **username_1**: What about a cycle entering from $u_1$ and leaving from $v_2$?  

---

