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:
- When $(\Delta_{in}, \Delta_{out}) = (1, d)$, DFVS is polynominal-time solvable.
- When $(\Delta_{in}, \Delta_{out}) \geq (2, 2)$, DFVS is $\mathsf{NP}$-hard.
- 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$?