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


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.


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.

  • $\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 '14 at 18:28

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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