<p><a href="http://www2.research.att.com/~mgcr/doc/sfsp.pdf" rel="nofollow">According to Festa, Pardalos and Resende</a> (link at the bottom of the Wikipedia page), the problem can be solved in polynomial time for various classes of graphs. At the risk of sounding harsh, I find parts of the text awkwardly unconvincing (e.g. "... it returns an optimal solution in polynomial time for certain types of graphs" without specifying which), but it might be an early draft that they put together in a rush. </p>

<p>Anyway, section 3.2 of that paper should help you find some leads.</p>

CC BY-SA 2.5
2011-03-14T20:27:20.063Z
2011-03-14T20:27:20.063Z
Anthony Labarre
<p>Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.</p>

CC BY-SA 2.5
2011-03-15T16:30:27.800Z
I don't think a tree decomposition helps with dynamic programming, since the treewidth will appear as the $c$ in an expression something like $c^k$, for FVS of size $k$.  Consider a path with $n/4$ vertices, with triangles connected to each point on the path (a total of $n$ vertices).  This has treewidth 2.  Yet a FVS must remove at least one vertex from each triangle, so at least $n/4$ vertices.  The published algorithms are fixed-parameter tractable for parameter $k$ being the size of the FVS, not $k$ being the treewidth.
András Salamon
CC BY-SA 2.5
2011-03-29T16:08:18.977Z
By the way, I got a bit confused at some point and thought that it was not known that FVS was polytime for fixed treewidth.  Indeed I could not find a credible reference to an algorithm, but I did find a couple of allusions to the fact that it is fairly easy.  In fact you can do it in linear time by maintaining a dynamic programming table for, given a tree decomposition bag $C$, every subset of $C$ times every partition of $C$.
Andrew D. King
CC BY-SA 2.5
2011-03-15T03:24:17.517Z
http://www.springerlink.com/content/264635x07pn55617/ This seems like it might be a relevant reference in that case.
Abel Molina
CC BY-SA 2.5
2011-03-15T04:13:00.543Z
Unfortunately, the FVS result claimed in that paper is incorrect. They claim a dynamic programming algorithm for FVS which runs in $O(2^{t+1})$ time, given a tree decomposition of width $t$. If true, this would imply an $O^*(2^{k})$-time FPT algorithm for FVS where $k$ is the size of the FVS sought and the star hides polynomial factors. AFAIK, the best known FPT algorithm at the time of publication of this paper took $O^{*}(2\log k+2\log\log k+18)^{k}$ time. The first $O^*(c^{k})$ algorithm dates from 2005, for $c=37.7$. (contd.)
gphilip
CC BY-SA 2.5
2011-03-15T04:24:17.507Z
(contd.) The current fastest published algorithm (after a series of improvements) runs in $O^*(3.83^{k})$ time (http://www.springerlink.com/content/f3726432823626n7/); a very recent paper on arxiv (http://arxiv.org/abs/1103.0534) gives a Monte-Carlo algorithm which runs in $O^{*}(3^{t})$ time given a tree decomposition of width $t$.

Of course, none of this per se makes the claim in the quoted paper incorrect, only improbable. There is a bug in their proof of correctness of the dynamic programming algorithm; finding it turned out to be an instructive exercise (in at least two ways!).
gphilip
CC BY-SA 2.5
2011-03-14T20:40:50.123Z
2011-03-14T20:40:50.123Z
Andrew D. King
<p>Kratsch, Müller and Todinca gave a polynomial-time algorithm for AT-free graphs.</p>

<ul>
<li>D. Kratsch, H. Müller and I. Todinca. Feedback vertex set on AT-free graphs, Discrete Applied Mathematics 156 (2008) pp. 1936-1947. <a href="http://dx.doi.org/10.1016/j.dam.2007.10.006">http://dx.doi.org/10.1016/j.dam.2007.10.006</a> (or <a href="http://lita.sciences.univ-metz.fr/~kratsch/publications/fvsATfree.pdf">http://lita.sciences.univ-metz.fr/~kratsch/publications/fvsATfree.pdf</a>)</li>
</ul>

CC BY-SA 2.5
2011-03-14T21:56:55.597Z
2011-03-14T21:56:55.597Z
Yoshio Okamoto
<p>It is solvable in linear time for reducible digraphs (that is, those for which there is only one entry point at most in each strongly connected subgraph; they occur naturally in compilation and program analysis, because the control-flow graphs of structured programs are reducible).</p>

<p>Adi Shamir <em>A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs</em>. SIAM J. Comput. 8(4): 645-655 (1979)</p>

CC BY-SA 3.0
2012-06-02T08:33:06.943Z
2012-06-02T08:33:06.943Z
David Monniaux
<p><strong>EDIT:</strong> The answer below seems to be incorrect, as I seem to have read the results of the paper (mentioned below) too superficially. <strong>:EDIT</strong> </p>

<p>If I understood correctly, the following paper shows (among other things) that FVS is solvable in polynomial time on graphs of maximum degree at most 3:</p>

<p>Cao, Yixin; Chen, Jianer; Liu, Yang (2010), <a href="http://arxiv.org/pdf/1004.1672v1" rel="nofollow"> On Feedback Vertex Set: New
Measure and New Structures</a> in Kaplan, Haim, "SWAT 2010", LNCS 6139: 93–104.</p>

<p><strong>Outline</strong></p>

<p>They study a slightly more general problem, namely DISJOINT-FVS, where in
addition to the parameters of FVS, two certain vertex sets V_1 and V_2 are
given. For details, see the paper. Then, ordinary FVS instances are a special
case of DISJOINT FVS instances where the given set V_2 equals the entire vertex
set, and V_2 is empty. They show roughly the following: </p>

<p>a) DISJOINT FVS can be reduced to DISJOINT FVS on graphs of minimum degree at
least 3 without increasing the maximum degree.</p>

<p>b) On 3-regular graphs, DISJOINT FVS instance can be solved in polynomial time. </p>

<p>Together, these two results show that FVS on graphs of maximum outdegree 3 can
be solved in polynomial time. Beware that I have not read the paper very
thoroughly, and may have misunderstood or misstated something, or even everything. </p>

<p><strong>Technical details:</strong></p>

<p>a) This is oversimplified. Only the maximum degree in the graph induced by V_1
is not increased.</p>

<p>b) Also oversimplified. If the graph induced by V_1 is 3-regular, then this
DISJOINT FVS instance can be solved in polynomial time. </p>

CC BY-SA 2.5
2011-04-06T07:26:38.513Z
Thanks for pointing this out. Then my answer was probably wrong. Could you please provide a pointer to the definition of "wall graphs"?
Hermann Gruber
CC BY-SA 2.5
2011-04-06T11:52:13.637Z
Apologies, these seem to be an alternative name for hexagonal grids; to make them degree 3 one adds edges around the perimeter between degree-2 vertices (this can be done retaining planarity).  See Stephan Kreutzer's _Algorithmic Meta-Theorems_ http://eccc.uni-trier.de/report/2009/147/ page 47 for a definition.
András Salamon
CC BY-SA 2.5
2011-03-15T13:02:02.077Z
(a),(b) together only yields a polytime algorithm for FVS if the input FVS has at most k vertices, and k is a very slowly growing function of n.  For the wall graphs (which have degree at most 3 but arbitrarily large treewidth), any FVS has size $\Omega(n)$ and can be found easily, but not by the method in this paper.
András Salamon
CC BY-SA 3.0
2011-03-14T22:26:40.737Z
2012-06-07T20:05:58.927Z
2012-06-07T20:05:58.927Z
Hermann Gruber
<p>The feedback vertex set problem (FVS) can be solved by dynamic programming on graph decompositions.
As mentioned in another reply was treewidth, the standard algorithm gives $tw^{tw} poly(n)$, but a more involved result gives a $c^{tw}poly(n)$ algorithm.
The problem with this is that we don't know many graph classes which have logarithmic tree-width hence this does not often lead to polynomial algorithms.
To solve FVS on a tree-decomposition we store a table of different subsolutions where each partition of a bag can represent a partial solution.</p>

<p>We extended the standard algorithm to clique-width in this article
<a href="http://www.sciencedirect.com/science/article/pii/S0195669812001497" rel="nofollow">Feedback vertex set on graphs of low clique-width</a>.
Although there are many graphs with low clique-width which does not have bounded treewidth, many of the well studied graphclasses have unbounded clique-width.
For clique-width we have an expectation of size $cw$ promising us that the partial solution union the expectation induces at most cw components, and for each of these cw components we have at most $3^{cw}$ different sets representing partial solutions (can be slightly improved to obtain a $cw^{cw}poly(n)$ runningtime.
The problem with clique-width is that we can not compute good clique-decompositions fast enough.</p>

<p>The result can be extended to a new parameter called Maximum Induced Matching width (MIM-width), see <a href="http://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf" rel="nofollow">My Thesis</a> where it is introduced.
Given a decomposition of MIM-width $mim$ we need a expectation of size $mim$ (at most $n^{mim}$ choices of expectation).
For each of the components in the solution union the expectation we need to store which vertices has 1 neighbour in the partial solution and which vertices has at least 2 neighbours in the partial solution, which is similar to what we did in <a href="http://www.sciencedirect.com/science/article/pii/S0304397513000595" rel="nofollow">Fast FPT algorithms for vertex subset and vertex partitioning problems using unions of neighbourhoods</a>.
In total this leads to a $n^{O(mim^2)}poly(n)$ time algorithm.
This result is not published.</p>

<p>Combining the results with the results of <a href="http://www.sciencedirect.com/science/article/pii/S0304397513000613" rel="nofollow">Graph classes with structured neighborhoods and algorithmic applications</a> saying that many graphclasses have constant MIM-width and such decompositions can be found, we get the following result:</p>

<p>The feedback vertex set problem can be solved in polynomial time on:</p>

<ul>
<li>Interval graphs (<a href="http://www2.research.att.com/~mgcr/doc/sfsp.pdf" rel="nofollow">Festa et al</a>)</li>
<li>Circular arc graphs</li>
<li>Circular permutation graphs</li>
<li>trapezoid graphs</li>
<li>convex graphs (known from <a href="http://www2.research.att.com/~mgcr/doc/sfsp.pdf" rel="nofollow">Festa et al</a>)</li>
<li>Dilworth $k$ graphs</li>
<li>$k$ polygon graphs</li>
<li>bi-interval graphs</li>
<li>complements of $k$-degenerate graphs</li>
</ul>

<p>In addition we have:</p>

<p>Graphs with FVS of size $O(log n)$
Cao, Yixin; Chen, Jianer; Liu, Yang (2010), <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-13731-0_10" rel="nofollow">On Feedback Vertex Set: New Measure and New Structures</a>, "SWAT 2010", LNCS 6139: 93–104. </p>

<p>$k K_2$-free graphs, an easy consequence of Belas and Yu is that there are polynomially many FVS's in such graphs.</p>

<p>Chordal graphs
<a href="http://www2.research.att.com/~mgcr/doc/sfsp.pdf" rel="nofollow">Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000)</a></p>

<p>Possibly Graphs of degree at most 3, see cstheory.stackexchange questions 12712 is-feedback-vertex-set-problem-is-solvable-in-polynomial-time-for-3-degree-bound</p>

CC BY-SA 3.0
2014-02-12T11:39:51.753Z
That last crossref seems to have been lost in translation: http://cstheory.stackexchange.com/q/12712
András Salamon
CC BY-SA 3.0
2014-02-11T15:48:45.890Z
2014-02-11T16:11:29.837Z
2014-02-11T16:11:29.837Z
Martin Vatshelle
<p>Feedback vertex set (FVS) problem is NP-complete for both undirected and directed graphs, and it is NP-complete even for bipartite graphs and tournaments.</p>

<p>Is there any special family of graphs other than trees for which FVS is solvable in polynomial time? I kindly request you to throw some light on it.</p>

CC BY-SA 2.5
2011-03-14T17:36:35.103Z
See http://en.wikipedia.org/wiki/Feedback_vertex_set for definition.  I cannot find any support for this article's claim that FVS can be decided in polynomial time for graphs of degree at most 3.
András Salamon
CC BY-SA 2.5
2011-03-14T22:27:59.223Z
I think that the reference you are looking for is:

 Cao, Yixin; Chen, Jianer; Liu, Yang (2010), On Feedback Vertex Set: New Measure and New Structures in Kaplan, Haim, "SWAT 2010", LNCS 6139: 93–104. 

See my answer below for an explanation why I think that this is so.
Hermann Gruber
CC BY-SA 2.5
2011-03-15T05:32:40.893Z
Looks like it is going to be a big-list. What do you think?
Hsien-Chih Chang 張顯之
<cc.complexity-theory><graph-algorithms>
Is feedback vertex set problem is solvable in polynomial time for some special graph
Prabu 
# Is feedback vertex set problem is solvable in polynomial time for some special graph

(Asked by: username_0 on 2011-03-14)

Feedback vertex set (FVS) problem is NP-complete for both undirected and directed graphs, and it is NP-complete even for bipartite graphs and tournaments.

Is there any special family of graphs other than trees for which FVS is solvable in polynomial time? I kindly request you to throw some light on it.

**Tags:** cc.complexity-theory, graph-algorithms
> **Comments:**
> **username_1**: See http://en.wikipedia.org/wiki/Feedback_vertex_set for definition.  I cannot find any support for this article's claim that FVS can be decided in polynomial time for graphs of degree at most 3.  
> **username_2**: I think that the reference you are looking for is:   Cao, Yixin; Chen, Jianer; Liu, Yang (2010), On Feedback Vertex Set: New Measure and New Structures in Kaplan, Haim, "SWAT 2010", LNCS 6139: 93–104.   See my answer below for an explanation why I think that this is so.  
> **username_3**: Looks like it is going to be a big-list. What do you think?  

---

## 6 answers

### Answer by username_4 on 2011-03-14. Score: 6 | Accepted answer

[According to Festa, Pardalos and Resende](http://www2.research.att.com/~mgcr/doc/sfsp.pdf) (link at the bottom of the Wikipedia page), the problem can be solved in polynomial time for various classes of graphs. At the risk of sounding harsh, I find parts of the text awkwardly unconvincing (e.g. "... it returns an optimal solution in polynomial time for certain types of graphs" without specifying which), but it might be an early draft that they put together in a rush.

Anyway, section 3.2 of that paper should help you find some leads.


---

### Answer by username_5 on 2011-03-14. Score: 10

Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.

> **Comments:**
> **username_6**: http://www.springerlink.com/content/264635x07pn55617/ This seems like it might be a relevant reference in that case.  
> **username_7**: Unfortunately, the FVS result claimed in that paper is incorrect. They claim a dynamic programming algorithm for FVS which runs in $O(2^{t+1})$ time, given a tree decomposition of width $t$. If true, this would imply an $O^*(2^{k})$-time FPT algorithm for FVS where $k$ is the size of the FVS sought and the star hides polynomial factors. AFAIK, the best known FPT algorithm at the time of publication of this paper took $O^{*}(2\log k+2\log\log k+18)^{k}$ time. The first $O^*(c^{k})$ algorithm dates from 2005, for $c=37.7$. (contd.)  
> **username_7**: (contd.) The current fastest published algorithm (after a series of improvements) runs in $O^*(3.83^{k})$ time (http://www.springerlink.com/content/f3726432823626n7/); a very recent paper on arxiv (http://arxiv.org/abs/1103.0534) gives a Monte-Carlo algorithm which runs in $O^{*}(3^{t})$ time given a tree decomposition of width $t$.  Of course, none of this per se makes the claim in the quoted paper incorrect, only improbable. There is a bug in their proof of correctness of the dynamic programming algorithm; finding it turned out to be an instructive exercise (in at least two ways!).  
> **username_1**: I don't think a tree decomposition helps with dynamic programming, since the treewidth will appear as the $c$ in an expression something like $c^k$, for FVS of size $k$.  Consider a path with $n/4$ vertices, with triangles connected to each point on the path (a total of $n$ vertices).  This has treewidth 2.  Yet a FVS must remove at least one vertex from each triangle, so at least $n/4$ vertices.  The published algorithms are fixed-parameter tractable for parameter $k$ being the size of the FVS, not $k$ being the treewidth.  
> **username_5**: By the way, I got a bit confused at some point and thought that it was not known that FVS was polytime for fixed treewidth.  Indeed I could not find a credible reference to an algorithm, but I did find a couple of allusions to the fact that it is fairly easy.  In fact you can do it in linear time by maintaining a dynamic programming table for, given a tree decomposition bag $C$, every subset of $C$ times every partition of $C$.  

---

### Answer by username_8 on 2011-03-14. Score: 6

Kratsch, Müller and Todinca gave a polynomial-time algorithm for AT-free graphs.

* D. Kratsch, H. Müller and I. Todinca. Feedback vertex set on AT-free graphs, Discrete Applied Mathematics 156 (2008) pp. 1936-1947. <http://dx.doi.org/10.1016/j.dam.2007.10.006> (or <http://lita.sciences.univ-metz.fr/~kratsch/publications/fvsATfree.pdf>)


---

### Answer by username_9 on 2012-06-02. Score: 3

It is solvable in linear time for reducible digraphs (that is, those for which there is only one entry point at most in each strongly connected subgraph; they occur naturally in compilation and program analysis, because the control-flow graphs of structured programs are reducible).

Adi Shamir *A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs*. SIAM J. Comput. 8(4): 645-655 (1979)


---

### Answer by username_2 on 2011-03-14. Score: 3

**EDIT:** The answer below seems to be incorrect, as I seem to have read the results of the paper (mentioned below) too superficially. **:EDIT**

If I understood correctly, the following paper shows (among other things) that FVS is solvable in polynomial time on graphs of maximum degree at most 3:

Cao, Yixin; Chen, Jianer; Liu, Yang (2010),  [On Feedback Vertex Set: New
Measure and New Structures](http://arxiv.org/pdf/1004.1672v1) in Kaplan, Haim, "SWAT 2010", LNCS 6139: 93–104.

**Outline**

They study a slightly more general problem, namely DISJOINT-FVS, where in
addition to the parameters of FVS, two certain vertex sets V\_1 and V\_2 are
given. For details, see the paper. Then, ordinary FVS instances are a special
case of DISJOINT FVS instances where the given set V\_2 equals the entire vertex
set, and V\_2 is empty. They show roughly the following:

a) DISJOINT FVS can be reduced to DISJOINT FVS on graphs of minimum degree at
least 3 without increasing the maximum degree.

b) On 3-regular graphs, DISJOINT FVS instance can be solved in polynomial time.

Together, these two results show that FVS on graphs of maximum outdegree 3 can
be solved in polynomial time. Beware that I have not read the paper very
thoroughly, and may have misunderstood or misstated something, or even everything.

**Technical details:**

a) This is oversimplified. Only the maximum degree in the graph induced by V\_1
is not increased.

b) Also oversimplified. If the graph induced by V\_1 is 3-regular, then this
DISJOINT FVS instance can be solved in polynomial time.

> **Comments:**
> **username_1**: (a),(b) together only yields a polytime algorithm for FVS if the input FVS has at most k vertices, and k is a very slowly growing function of n.  For the wall graphs (which have degree at most 3 but arbitrarily large treewidth), any FVS has size $\Omega(n)$ and can be found easily, but not by the method in this paper.  
> **username_2**: Thanks for pointing this out. Then my answer was probably wrong. Could you please provide a pointer to the definition of "wall graphs"?  
> **username_1**: Apologies, these seem to be an alternative name for hexagonal grids; to make them degree 3 one adds edges around the perimeter between degree-2 vertices (this can be done retaining planarity).  See Stephan Kreutzer's _Algorithmic Meta-Theorems_ http://eccc.uni-trier.de/report/2009/147/ page 47 for a definition.  

---

### Answer by username_10 on 2014-02-11. Score: 2

The feedback vertex set problem (FVS) can be solved by dynamic programming on graph decompositions.
As mentioned in another reply was treewidth, the standard algorithm gives $tw^{tw} poly(n)$, but a more involved result gives a $c^{tw}poly(n)$ algorithm.
The problem with this is that we don't know many graph classes which have logarithmic tree-width hence this does not often lead to polynomial algorithms.
To solve FVS on a tree-decomposition we store a table of different subsolutions where each partition of a bag can represent a partial solution.

We extended the standard algorithm to clique-width in this article
[Feedback vertex set on graphs of low clique-width](http://www.sciencedirect.com/science/article/pii/S0195669812001497).
Although there are many graphs with low clique-width which does not have bounded treewidth, many of the well studied graphclasses have unbounded clique-width.
For clique-width we have an expectation of size $cw$ promising us that the partial solution union the expectation induces at most cw components, and for each of these cw components we have at most $3^{cw}$ different sets representing partial solutions (can be slightly improved to obtain a $cw^{cw}poly(n)$ runningtime.
The problem with clique-width is that we can not compute good clique-decompositions fast enough.

The result can be extended to a new parameter called Maximum Induced Matching width (MIM-width), see [My Thesis](http://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf) where it is introduced.
Given a decomposition of MIM-width $mim$ we need a expectation of size $mim$ (at most $n^{mim}$ choices of expectation).
For each of the components in the solution union the expectation we need to store which vertices has 1 neighbour in the partial solution and which vertices has at least 2 neighbours in the partial solution, which is similar to what we did in [Fast FPT algorithms for vertex subset and vertex partitioning problems using unions of neighbourhoods](http://www.sciencedirect.com/science/article/pii/S0304397513000595).
In total this leads to a $n^{O(mim^2)}poly(n)$ time algorithm.
This result is not published.

Combining the results with the results of [Graph classes with structured neighborhoods and algorithmic applications](http://www.sciencedirect.com/science/article/pii/S0304397513000613) saying that many graphclasses have constant MIM-width and such decompositions can be found, we get the following result:

The feedback vertex set problem can be solved in polynomial time on:

* Interval graphs ([Festa et al](http://www2.research.att.com/~mgcr/doc/sfsp.pdf))
* Circular arc graphs
* Circular permutation graphs
* trapezoid graphs
* convex graphs (known from [Festa et al](http://www2.research.att.com/~mgcr/doc/sfsp.pdf))
* Dilworth $k$ graphs
* $k$ polygon graphs
* bi-interval graphs
* complements of $k$-degenerate graphs

In addition we have:

Graphs with FVS of size $O(log n)$
Cao, Yixin; Chen, Jianer; Liu, Yang (2010), [On Feedback Vertex Set: New Measure and New Structures](http://link.springer.com/chapter/10.1007%2F978-3-642-13731-0_10), "SWAT 2010", LNCS 6139: 93–104.

$k K\_2$-free graphs, an easy consequence of Belas and Yu is that there are polynomially many FVS's in such graphs.

Chordal graphs
[Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000)](http://www2.research.att.com/~mgcr/doc/sfsp.pdf)

Possibly Graphs of degree at most 3, see cstheory.stackexchange questions 12712 is-feedback-vertex-set-problem-is-solvable-in-polynomial-time-for-3-degree-bound

> **Comments:**
> **username_1**: That last crossref seems to have been lost in translation: http://cstheory.stackexchange.com/q/12712  

---

