Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NP-HARDNESS OF APPROXIMATION:
Reports tagged with NP-hardness of approximation:
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 >>>

TR14-043 | 2nd April 2014
Venkatesan Guruswami, Euiwoong Lee

#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

ISSN 1433-8092 | Imprint