文章基本信息

标题：Simple Proof of Hardness of Feedback Vertex Set
本地全文：下载
作者：Venkatesan Guruswami ; Euiwoong Lee
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2016
卷号：12
页码：1-11
出版社：University of Chicago
摘要：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 efficient constant-factor approximation is ruled out under the Unique Games Conjecture (UGC). We give a simpler proof that Feedback Vertex Set is hard to approximate within any constant factor, assuming UGC
关键词：inapproximability; UG-hardness; Feedback Vertex Set