13
$\begingroup$

Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?

$\endgroup$

5 Answers 5

16
$\begingroup$

According to Garey and Johnson's book Vertex Cover is NP-complete on planar graphs of maximum degree four. Using a simple reduction from Vertex Cover to Feedback Vertex Set should give maximum degree eight and preserve planarity.

VC to FVS: Replace each edge by a triangle (or a double edge).

One note: Garey and Johnson also state that directed FVS is NP-complete on planar digraphs with no in- or out-degree exceeding two. They do not specifically mention undirected FVS under such restrictions.

$\endgroup$
14
$\begingroup$

The answer is: FVS is NP-complete on undirected planar graphs of maximum degree $4$; proved by Speckenmeyer, see here. By subdividing each edge by one new vertex, it easily follows that

FVS is NP-complete even on undirected bipartite planar graphs of maximum degree $4$.

The degree constraint is best possibe, as FVS is polynomial for graphs of maximum degree at most three; see here.

Edit: Ernst de Ridder's graphclasses.org now contains all available information about FVS; including circa 550 polynomially solvable and circa 250 NP-c cases.

$\endgroup$
1
  • $\begingroup$ would you please explain more about the reduction, which is far from clear from me. I don't have Speckenmeyer's thesis at hand (even I had, I won't be able to understand German). But I do have the paper you mentioned, which, however, only refers to his thesis. On the other hand, I know that it's NP-hard on general graphs of maximum degree 4, as shown by Romeo Rizzi doi.org/10.1007/s00453-007-9112-8. Thanks! $\endgroup$
    – Yixin Cao
    Apr 5, 2014 at 18:28
5
$\begingroup$

According to Wikipedia Garey & Johnson also showed that " Vertex cover remains NP-complete ... even in planar graphs of degree at most 3."

Thus FVS is hard on planar graphs with maximum degree 6.

$\endgroup$
2
$\begingroup$

Apparently, in Speckenmeyer's PhD thesis, he demonstrates that the feedback vertex set problem is NP-hard for graphs of maximum degree 4. This claim appears here, for example.

For cubic graphs, the problem seems to be solvable in polynomial time. First, Speckenmeyer demonstrates that for cubic graphs, the minimum-size feedback vertex set is equal to $n/2-z(G)+1$, where $n$ is the number of vertices and $z$ is the size of the largest nonseparating independent set. Huang and Liu demonstrate that for cubic graphs, $z(G)$ is equal to the maximum genus of $G$, which can be calculated in polynomial time using the algorithm of Furst, Gross, and McGeoch.

Edit: didn't examine vb le's edit carefully enough...

$\endgroup$
1
$\begingroup$

gadgets

Here are the two gadgets Speckenmeyer used in his Ph.D. thesis. We can start from planar graphs with maximum degree six, by a reduction from the vertex cover problem on cubic planar graphs. (Actually, we can start from a general planar graph and use similar gadgets to reduce its maximum degrees.) We replace a vertex $x$ of degree six with the left gadget and a vertex $x$ of degree five with the right gadget. A solution $S$ to the original problem will be translated as follows:

if $x\in S$, then we take $\{u_2, u_4, v_3\}$; otherwise $\{v_1, v_5\}$.

Since the feedback vertex set problem can be solved in polynomial time in cubic graphs, even if they are not planar, the issue is settled. Source: http://dx.doi.org/10.1016/0012-365X(88)90226-9

$\endgroup$
1
  • $\begingroup$ This is Speckenmeyer's Ph.D. thesis written in German. $\endgroup$
    – Blanco
    Mar 4, 2023 at 9:34

Your Answer

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

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