Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Feedback Arc Set:
TR06-144 | 21st November 2006
Claire Kenyon-Mathieu, Warren Schudy

How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking ... more >>>

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