Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with cycle transversal:
TR14-006 | 16th January 2014
Venkatesan Guruswami, Euiwoong Lee

Inapproximability of Feedback Vertex Set for Bounded Length Cycles

Revisions: 1

The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation ... more >>>

ISSN 1433-8092 | Imprint