4
$\begingroup$

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$?
$\endgroup$

2 Answers 2

1
$\begingroup$

gadget

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yixin Cao
    Mar 3 at 8:33
  • $\begingroup$ Your construction of the gadget is much helpful. Perhaps, this problem would have been settled if my reduction for the planar version is correct. $\endgroup$
    – Blanco
    Mar 6 at 4:43
1
$\begingroup$

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

enter image description here

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

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

$\endgroup$
1
  • $\begingroup$ What about a cycle entering from $u_1$ and leaving from $v_2$? $\endgroup$
    – Yixin Cao
    Mar 4 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.