Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

up vote 13 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
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! –  Yixin Cao Apr 5 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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