<p><strong>The answer is:</strong> FVS is NP-complete on undirected planar graphs of maximum degree $4$; proved by Speckenmeyer, see <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract" rel="nofollow noreferrer">here</a>. By subdividing each edge by one new vertex, it easily follows that </p>

<blockquote>
  <p>FVS is NP-complete even on undirected bipartite planar graphs of maximum 
  degree $4$.</p>
</blockquote>

<p>The degree constraint is best possibe, as FVS is polynomial for graphs of maximum degree at most three; see <a href="https://cstheory.stackexchange.com/questions/12712/is-feedback-vertex-set-problem-is-solvable-in-polynomial-time-for-3-degree-bound?rq=1">here</a>. </p>

<p><strong>Edit:</strong> Ernst de Ridder's <a href="http://graphclasses.org/classes/problem_Feedback_vertex_set.html" rel="nofollow noreferrer">graphclasses.org</a> now contains all available information about FVS; including circa 550 polynomially solvable and circa 250 NP-c cases. </p>

CC BY-SA 3.0
2014-04-05T18:28:09.450Z
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 http://doi.org/10.1007/s00453-007-9112-8. Thanks!
Yixin Cao
CC BY-SA 3.0
2013-01-21T23:45:38.970Z
2013-02-25T20:34:08.573Z
2017-04-13T12:32:28.743Z
vb le
<p>According to Wikipedia Garey &amp; Johnson also showed that " Vertex cover remains NP-complete ... even in planar graphs of degree at most 3."</p>

<p>Thus FVS is hard on planar graphs with maximum degree 6.</p>

CC BY-SA 3.0
2012-07-20T11:44:29.607Z
2013-02-01T00:16:34.887Z
2013-02-01T00:16:34.887Z
101011
<p>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 <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract" rel="nofollow">here</a>, for example.</p>

<p>For cubic graphs, the problem seems to be solvable in polynomial time. First, <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract" rel="nofollow">Speckenmeyer</a> 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. <a href="http://www.sciencedirect.com/science/article/pii/S0012365X96002993" rel="nofollow">Huang and Liu</a> 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 <a href="http://dl.acm.org/citation.cfm?id=44485" rel="nofollow">Furst, Gross, and McGeoch</a>.</p>

<p>Edit: didn't examine vb le's edit carefully enough...</p>

CC BY-SA 3.0
2013-02-26T10:45:48.710Z
2013-02-26T10:55:22.103Z
2013-02-26T10:55:22.103Z
Timothy Sun
<p><a href="https://i.sstatic.net/pHlmJ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pHlmJ.png" alt="gadgets" /></a></p>
<p>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 <span class="math-container">$x$</span> of degree six with the left gadget and a vertex <span class="math-container">$x$</span> of degree five with the right gadget. A solution <span class="math-container">$S$</span> to the original problem will be translated as follows:</p>
<p>if <span class="math-container">$x\in S$</span>, then we take <span class="math-container">$\{u_2, u_4, v_3\}$</span>; otherwise <span class="math-container">$\{v_1, v_5\}$</span>.</p>
<p>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: <a href="http://dx.doi.org/10.1016/0012-365X(88)90226-9" rel="nofollow noreferrer">http://dx.doi.org/10.1016/0012-365X(88)90226-9</a></p>

CC BY-SA 4.0
2023-03-04T09:34:39.823Z
[This](https://www.researchgate.net/publication/269029032_Untersuchungen_zum_Feedback_Vertex_Set_Problem_in_ungerichteten_Graphen) is Speckenmeyer's Ph.D. thesis written in German.
Blanco
CC BY-SA 4.0
2023-03-03T09:00:40.940Z
2023-03-03T09:00:40.940Z
Yixin Cao
<p>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.</p>

<p>VC to FVS: Replace each edge by a triangle (or a double edge).</p>

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

CC BY-SA 3.0
2012-03-30T08:15:14.477Z
2012-03-30T08:15:14.477Z
Stefan Kratsch
<p>Is it known whether the <a href="http://en.wikipedia.org/wiki/Feedback_vertex_set">feedback vertex set</a> problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?</p>

<cc.complexity-theory><reference-request><graph-algorithms><np-hardness>
Is the feedback vertex set problem on planar bounded degree graphs hard?
marc
# Is the feedback vertex set problem on planar bounded degree graphs hard?

(Asked by: username_0 on 2012-03-30)

Is it known whether the [feedback vertex set](http://en.wikipedia.org/wiki/Feedback_vertex_set) problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, np-hardness

---

## 5 answers

### Answer by username_6 on 2012-03-30. Score: 16 | Accepted answer

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.


---

### Answer by username_1 on 2013-01-21. Score: 14

**The answer is:** FVS is NP-complete on undirected planar graphs of maximum degree $4$; proved by Speckenmeyer, see [here](http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract). 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](https://cstheory.stackexchange.com/questions/12712/is-feedback-vertex-set-problem-is-solvable-in-polynomial-time-for-3-degree-bound?rq=1).

**Edit:** Ernst de Ridder's [graphclasses.org](http://graphclasses.org/classes/problem_Feedback_vertex_set.html) now contains all available information about FVS; including circa 550 polynomially solvable and circa 250 NP-c cases.

> **Comments:**
> **username_2**: 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 http://doi.org/10.1007/s00453-007-9112-8. Thanks!  

---

### Answer by username_3 on 2012-07-20. Score: 5

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.


---

### Answer by username_4 on 2013-02-26. Score: 2

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](http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract), for example.

For cubic graphs, the problem seems to be solvable in polynomial time. First, [Speckenmeyer](http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190120311/abstract) 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](http://www.sciencedirect.com/science/article/pii/S0012365X96002993) 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](http://dl.acm.org/citation.cfm?id=44485).

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


---

### Answer by username_2 on 2023-03-03. Score: 1

[![gadgets](https://i.sstatic.net/pHlmJ.png)](https://i.sstatic.net/pHlmJ.png)

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>

> **Comments:**
> **username_5**: [This](https://www.researchgate.net/publication/269029032_Untersuchungen_zum_Feedback_Vertex_Set_Problem_in_ungerichteten_Graphen) is Speckenmeyer's Ph.D. thesis written in German.  

---

