×

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