Venkatesan Guruswami, Euiwoong Lee

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

Venkatesan Guruswami, Euiwoong Lee

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