# zbMATH — the first resource for mathematics

Untersuchungen zum Feedback Vertex Problem in ungerichteten Graphen. (German) Zbl 0534.68046
Fachbereich Mathematik/Informatik der Universität-Gesamthochschule- Paderborn. 61 S. (1983).
Let FVS be the problem of finding a minimum feedback vertex set of a graph $$G=(V,E)$$, i.e. a minimum cardinality subset V’$$\subset V$$, such that G-V’ is cycle free. Let f(G) be the cardinality of V’. Some results concerning FVS are proved:
1. For unrestricted graphs G: There is an $$O(| V|)$$ algorithm for FVS if G is a cactus, i.e. if two different cycles in G have only one vertex in common.
2. For graphs G with maximal vertex degree 4: FVS is NP-complete even if G is planar.
3. For graphs G with maximal vertex degree 3: There is an $$O(| V|)$$ algorithm for FVS, if G possesses a vertex cover by triangles.- FVS is polynomially equivalent to the problem of finding a minimum connected vertex cover.- There are two similar $$O(| V|^ 2)$$ approximation algorithms for FVS yielding feedback vertex sets $$V_ A$$. One with $$| V_ A| \leq 2/5(| V| +1)$$ and $$| V_ A| \lessgtr 3/2f(G)$$, and one with $$| V_ A| \leq 3/8| V| +1$$. Therefore $$f(G)\lessgtr 3/8| V| +1$$.- $$f(G)\lessgtr | V| /4+k(G)+1/2$$, where k(G) is the maximal number of disjoint cycles in F.- The bounds given are sharp.- It remains open, whether FVS is NP-complete.
Reviewer: J.Ebert

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)