4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ See 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. $\endgroup$
    – András Salamon
    Commented Mar 14, 2011 at 17:36
  • $\begingroup$ 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. $\endgroup$
    – Hermann Gruber
    Commented Mar 14, 2011 at 22:27
  • $\begingroup$ Looks like it is going to be a big-list. What do you think? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Mar 15, 2011 at 5:32

6 Answers 6

Reset to default
6
$\begingroup$

According to Festa, Pardalos and Resende (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.

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ springerlink.com/content/264635x07pn55617 This seems like it might be a relevant reference in that case. $\endgroup$
    – Abel Molina
    Commented Mar 15, 2011 at 3:24
  • 3
    $\begingroup$ 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.) $\endgroup$
    – gphilip
    Commented Mar 15, 2011 at 4:13
  • 2
    $\begingroup$ (contd.) The current fastest published algorithm (after a series of improvements) runs in $O^*(3.83^{k})$ time (springerlink.com/content/f3726432823626n7); a very recent paper on arxiv (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!). $\endgroup$
    – gphilip
    Commented Mar 15, 2011 at 4:24
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Mar 15, 2011 at 16:30
  • $\begingroup$ 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$. $\endgroup$
    – Andrew D. King
    Commented Mar 29, 2011 at 16:08
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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)

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ (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. $\endgroup$
    – András Salamon
    Commented Mar 15, 2011 at 13:02
  • $\begingroup$ Thanks for pointing this out. Then my answer was probably wrong. Could you please provide a pointer to the definition of "wall graphs"? $\endgroup$
    – Hermann Gruber
    Commented Apr 6, 2011 at 7:26
  • 1
    $\begingroup$ 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 eccc.uni-trier.de/report/2009/147 page 47 for a definition. $\endgroup$
    – András Salamon
    Commented Apr 6, 2011 at 11:52
2
$\begingroup$

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. 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 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. 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 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)
  • Circular arc graphs
  • Circular permutation graphs
  • trapezoid graphs
  • convex graphs (known from Festa et al)
  • 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, "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)

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

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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