Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM FEEDBACK VERTEX SET

• INSTANCE: Directed graph $G=\left(V,A\right)$.
• SOLUTION: A feedback vertex set, i.e., a subset $V' \subseteq V$ such that V' contains at least one vertex from every directed cycle in G.
• MEASURE: Cardinality of the feedback vertex set, i.e., $\vert V'\vert$.

  
  

• Good News: Approximable within $O(\log \vert V\vert \log\log \vert V\vert)$ [435] and [148].
• Bad News: APX-hard [282].
• Comment: Transformations from MINIMUM VERTEX COVER and MINIMUM FEEDBACK ARC SET [46]. On undirected graphs the problem is APX-complete and approximable within 2, even if the vertices are weighted [50]. The generalized variation in which the input is extended with a subset S of vertices and arcs, and the problem is to find a vertex set that contains at least one vertex from every directed cycle that intersects S, is approximable within $O(\min(\log \vert V\vert\log\log \vert V\vert,\log^2 \vert S\vert))$ on directed graphs [148] and within 8 on undirected graphs [149]. All these problems are approximable within 9/4 for planar graphs [199]. The constrained variation in which the input is extended with a positive integer k and a subset S of V, and the problem is to find the feedback vertex set of size k that contains the largest number of vertices from S, is not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [476].
• Garey and Johnson: GT7