<p>The relevant references appear to be:</p>

<p>Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986).  <a href="http://dx.doi.org/10.1016/0012-365X%2888%2990226-9">Discrete Math. 72 (1988), no. 1-3, 355–360</a>.</p>

<p>Li, Deming; Liu, Yanpei. A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Math. Sci. 19 (1999), no. 4, 375–381. </p>

<p>(Warning: I have not read either one but they both claim to solve the problem in polynomial time. I don't think the difference between 3-regular and max degree three is important for this problem.)</p>

CC BY-SA 3.0
2012-09-24T01:31:54.820Z
2012-09-24T01:31:54.820Z
David Eppstein
<p>Li and Liu's algorithm is incorrect (see below).  Ueno et al.'s algorithm is correct, and a similar algorithm can be found in Furst et al. <a href="http://doi.org/10.1145/44483.44485" rel="nofollow noreferrer">1</a>.  Both algorithms reduce the problem to the polynomial-solvable matroid parity problem [3].</p>

<p>Its reduction from VC ensures the NP-hardness for degree-6 bounded graph!  As VC is already NP-hard on cubic graphs. Speckenmeyer has claimed that his thesis [4] contains the proof of NP-hardness of FVS on planar graphs of maximum degree four, but it's very hard to find (I'll greatly appreciate if who have access to his thesis can send me a copy). Fortunately, a new proof of
the NP-hardness of degree-four bounded graphs can be found in <a href="http://doi.org/10.1007/s00453-007-9112-8" rel="nofollow noreferrer">2</a>:</p>

<p>Remarks on <a href="http://doi.org/10.1007/s00453-007-9112-8" rel="nofollow noreferrer">2</a>: 
 - In fact, he proved that the problem is APX-hard, but it is easy to verify
that his reductions are also valid for the proof of NP-hardness of the problem.
 - Its reduction does NOT apply to planar graphs. </p>

<ol>
<li>Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch, “Finding a maximum-genus graph imbedding,” Journal of the ACM, vol. 35, no. 3, pp. 523–534, 1988. <a href="http://doi.org/10.1145/44483.44485" rel="nofollow noreferrer">10.1145/44483.44485</a></li>
<li>Rizzi, R.: Weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402-424 (2009) <a href="http://doi.org/10.1007/s00453-007-9112-8" rel="nofollow noreferrer">10.1007/s00453-007-9112-8</a></li>
<li>László Lovász, “The matroid matching problem,” in Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungary, 1980, pp. 495–517.</li>
<li>Ewald Speckenmeyer, “Untersuchungen zum feedback vertex set problem in ungerichteten graphen,” PhD thesis, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.</li>
</ol>

CC BY-SA 3.0
2012-09-24T15:32:28.927Z
Is there a simple reason why it's "clearly incorrect" ?
Suresh Venkat
CC BY-SA 3.0
2014-04-10T00:18:27.193Z
@SureshVenkat Sorry for the late reply: I just noticed this question.
The critical mistake is in Theorem 4.2, which is the main theorem of this paper. It claims that given a adjacency matching $M$ and a pair of edges $\{e_1,e_2\}$ in a bigger adjacency matching $M'$ but not in $M$, they can augment $M$ by adding $\{e_1,e_2\}$ to $M$.  This is clearly wrong, because the definition of adjacency matching requires the deletion of all edges of an adjacency matching does NOT disconnected the graph.
Yixin Cao
CC BY-SA 3.0
2014-04-10T00:18:45.470Z
continued... One can easily get a matching $M$ with only one pair, which meets at vertex $v$, and another matching $M'$ of two pairs, one of which uses the other edge incident to $v$. This pair cannot be used to augment $M$. 
Moreover, Lemma 4.1 contains also critical mistakes, but I don't remember the details at this moement. (I detected them in earlier 2009, and I tried to contact the authors immediately, but unfortunately I never got any response.)
Yixin Cao
CC BY-SA 4.0
2012-09-24T11:42:45.823Z
2020-05-15T15:41:40.120Z
2020-05-15T15:41:40.120Z
Yixin Cao
<p>Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-<span class="math-container">$8$</span> bounded graphs due to a reduction from vertex cover.
The <a href="http://en.wikipedia.org/wiki/Feedback_vertex_set" rel="nofollow noreferrer">Wikipedia article</a> says that it is poly-time solvable for degree-<span class="math-container">$3$</span> bounded graphs and is NP-complete for degree-<span class="math-container">$4$</span> bounded graphs. But I have not been able to find any proof for this anywhere. Is it true?</p>
<blockquote>
<p>What is the minimum <span class="math-container">$d$</span> such that FVS in degree-<span class="math-container">$d$</span> bounded graphs is
NP-complete?</p>
</blockquote>

CC BY-SA 4.0
2021-02-14T10:22:07.520Z
@user12110 Yes it also remains hard. Given a degree-4 bounded graph, one can remove the degree-0 and degree-1 vertices and smooth the degree-2 vertices firstly. For each pair of degree-3 vertices $(v,u)$, we can add a vertex $w$ with a loop and incident edges $wv$,$wu$.
Blanco
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness><bounded-degree>
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Davis Issac
# Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

(Asked by: username_0 on 2012-09-23)

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The [Wikipedia article](http://en.wikipedia.org/wiki/Feedback_vertex_set) says that it is poly-time solvable for degree-$3$ bounded graphs and is NP-complete for degree-$4$ bounded graphs. But I have not been able to find any proof for this anywhere. Is it true?

> What is the minimum $d$ such that FVS in degree-$d$ bounded graphs is
> NP-complete?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness, bounded-degree

> **Comments:**
> **username_1**: @user12110 Yes it also remains hard. Given a degree-4 bounded graph, one can remove the degree-0 and degree-1 vertices and smooth the degree-2 vertices firstly. For each pair of degree-3 vertices $(v,u)$, we can add a vertex $w$ with a loop and incident edges $wv$,$wu$.  

---

## 2 answers

### Answer by username_3 on 2012-09-24. Score: 13 | Accepted answer

Li and Liu's algorithm is incorrect (see below). Ueno et al.'s algorithm is correct, and a similar algorithm can be found in Furst et al. [1](http://doi.org/10.1145/44483.44485). Both algorithms reduce the problem to the polynomial-solvable matroid parity problem [3].

Its reduction from VC ensures the NP-hardness for degree-6 bounded graph! As VC is already NP-hard on cubic graphs. Speckenmeyer has claimed that his thesis [4] contains the proof of NP-hardness of FVS on planar graphs of maximum degree four, but it's very hard to find (I'll greatly appreciate if who have access to his thesis can send me a copy). Fortunately, a new proof of
the NP-hardness of degree-four bounded graphs can be found in [2](http://doi.org/10.1007/s00453-007-9112-8):

Remarks on [2](http://doi.org/10.1007/s00453-007-9112-8):
- In fact, he proved that the problem is APX-hard, but it is easy to verify
that his reductions are also valid for the proof of NP-hardness of the problem.
- Its reduction does NOT apply to planar graphs.

1. Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch, “Finding a maximum-genus graph imbedding,” Journal of the ACM, vol. 35, no. 3, pp. 523–534, 1988. [10.1145/44483.44485](http://doi.org/10.1145/44483.44485)
2. Rizzi, R.: Weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402-424 (2009) [10.1007/s00453-007-9112-8](http://doi.org/10.1007/s00453-007-9112-8)
3. László Lovász, “The matroid matching problem,” in Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungary, 1980, pp. 495–517.
4. Ewald Speckenmeyer, “Untersuchungen zum feedback vertex set problem in ungerichteten graphen,” PhD thesis, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.

> **Comments:**
> **username_4**: Is there a simple reason why it's "clearly incorrect" ?  
> **username_3**: @SureshVenkat Sorry for the late reply: I just noticed this question. The critical mistake is in Theorem 4.2, which is the main theorem of this paper. It claims that given a adjacency matching $M$ and a pair of edges $\{e_1,e_2\}$ in a bigger adjacency matching $M'$ but not in $M$, they can augment $M$ by adding $\{e_1,e_2\}$ to $M$.  This is clearly wrong, because the definition of adjacency matching requires the deletion of all edges of an adjacency matching does NOT disconnected the graph.  
> **username_3**: continued... One can easily get a matching $M$ with only one pair, which meets at vertex $v$, and another matching $M'$ of two pairs, one of which uses the other edge incident to $v$. This pair cannot be used to augment $M$.  Moreover, Lemma 4.1 contains also critical mistakes, but I don't remember the details at this moement. (I detected them in earlier 2009, and I tried to contact the authors immediately, but unfortunately I never got any response.)  

---

### Answer by username_2 on 2012-09-24. Score: 10

The relevant references appear to be:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). [Discrete Math. 72 (1988), no. 1-3, 355–360](http://dx.doi.org/10.1016/0012-365X%2888%2990226-9).

Li, Deming; Liu, Yanpei. A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Math. Sci. 19 (1999), no. 4, 375–381.

(Warning: I have not read either one but they both claim to solve the problem in polynomial time. I don't think the difference between 3-regular and max degree three is important for this problem.)


---

