NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Question

My question is the directed version of this one. (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) 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.
• 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$?

Answer 1

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\}$.

Answer 2

Thanks to Prof. @Yixin Cao'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, $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$.

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$.

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)$.