20
$\begingroup$

Feedback Vertex Set 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 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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Does anybody know if the problem hard on degree 4 regular undirected graphs ? $\endgroup$ – user12110 Oct 16 '12 at 16:04
11
$\begingroup$

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

Remarks on 2: - 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
  2. Rizzi, R.: Weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402-424 (2009) 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.
Improve this answer
$\endgroup$
  • 9
    $\begingroup$ Is there a simple reason why it's "clearly incorrect" ? $\endgroup$ – Suresh Venkat Sep 24 '12 at 15:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Yixin Cao Apr 10 '14 at 0:18
  • $\begingroup$ 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.) $\endgroup$ – Yixin Cao Apr 10 '14 at 0:18
10
$\begingroup$

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.

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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