Simple Proof of Hardness of Feedback Vertex Set

by Venkatesan Guruswami and Euiwoong Lee

Theory of Computing, Volume 12(6), pp. 1-11, 2016

Bibliography with links to cited articles

[1]   Vineet Bafna, Piotr Berman, and Toshihiro Fujito: Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Proc. 6th Internat. Symp. Alg. Comput. (ISAAC’95), pp. 142–151. Springer, 1995. [doi:10.1007/BFb0015417]

[2]   Nikhil Bansal and Subhash Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]

[3]   Ann Becker and Dan Geiger: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83(1):167–188, 1996. [doi:10.1016/0004-3702(95)00004-6]

[4]   Hans L. Bodlaender: On disjoint cycles. Internat. J. Found. Comput. Sci., 5(1):59–68, 1994. Preliminary version in WG’91. [doi:10.1142/S0129054194000049]

[5]   Jianer Chen, Yang Liu, Songjian Lu, Barry O’sullivan, and Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5):21:1–21:19, 2008. Preliminary version in STOC’08. [doi:10.1145/1411509.1411511]

[6]   Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, and Dániel Marx: Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms, 11(4):28:1–28:28, 2015. Preliminary version in ICALP’12. [doi:10.1145/2700209, arXiv:1205.1271]

[7]   Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, and David P. Williamson: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Research Lett., 22(4-5):111–118, 1998. [doi:10.1016/S0167-6377(98)00021-2]

[8]   Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math., 27(1):290–309, 2013. Preliminary version in ICALP’11. [doi:10.1137/110843071, arXiv:1004.2972]

[9]   Irit Dinur and Shmuel Safra: On the hardness of approximating minimum vertex cover. Ann. of Math., 162(1):439–485, 2005. Preliminary version in STOC’02. [doi:10.4007/annals.2005.162.439]

[10]   Guy Even, Joseph Seffi Naor, Satish Rao, and Baruch Schieber: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM, 47(4):585–616, 2000. Preliminary version in FOCS’95. [doi:10.1145/347476.347478]

[11]   Guy Even, Joseph Seffi Naor, Baruch Schieber, and Madhu Sudan: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. Preliminary version in IPCO’95. [doi:10.1007/PL00009191]

[12]   Venkatesan Guruswami, Johan Hĺstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878–914, 2011. Preliminary versions in FOCS’08 and ECCC. [doi:10.1137/090756144]

[13]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[14]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03. [doi:10.1016/j.jcss.2007.06.019]

[15]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x, arXiv:math/0703683]

[16]   Paul D. Seymour: Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995. [doi:10.1007/BF01200760]

[17]   Ola Svensson: Hardness of vertex deletion and project scheduling. Theory of Computing, 9(24):759–781, 2013. Preliminary version in APPROX’12. [doi:10.4086/toc.2013.v009a024, arXiv:1206.3408]