Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs

by Per Austrin, Subhash Khot, and Muli Safra

Theory of Computing, Volume 7(3), pp. 27-43, 2011

Bibliography with links to cited articles

[1]   Per Austrin: Balanced Max 2-Sat might not be the hardest. In Proc. 39th STOC, pp. 189–197. ACM Press, 2007. Full version available as ECCC Report TR06-088. [doi:10.1145/1250790.1250818]

[2]   Nikhil Bansal and Subhash Khot: Optimal long code test with one free bit. In Proc. 50th FOCS, pp. 453–462. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.23]

[3]   Nikhil Bansal and Subhash Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Intern. Colloq. Autom. Lang. Program. (ICALP), number 6198 in Lecture Notes in Comput. Sci., pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]

[4]   Etienne de Klerk, Dmitrii V. Pasechnik, and Joost P. Warners: On approximate graph colouring and MAX-k-CUT algorithms based on the ϑ-function. J. Comb. Optim., 8(3):267–294, 2004. [doi:10.1023/B:JOCO.0000038911.67280.3f]

[5]   Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. [doi:10.1137/07068062X]

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

[7]   Uriel Feige: Approximating maximum clique by removing subgraphs. SIAM J. Discrete Math., 18(2):219–225, 2004. [doi:10.1137/S089548010240415X]

[8]   Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proc. 49th FOCS, pp. 573–582. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.51]

[9]   Magnús M. Halldórsson: Approximations of weighted independent set and hereditary subset problems. In Proc. 5th Ann. Intern. Conf. Comput. Combin. (COCOON), volume 1627 of Lecture Notes in Comput. Sci., pp. 261–270. Springer, 1999. [doi:10.1007/3-540-48686-0_26]

[10]   Eran Halperin: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput., 31(5):1608–1623, 2002. [doi:10.1137/S0097539700381097]

[11]   Johan Håstad: Clique is hard to approximate within n1-ϵ. Acta Math., 48(4):105–142, 1999. [doi:10.1007/BF02392825]

[12]   George Karakostas: A better approximation ratio for the vertex cover problem. In Proc. 32nd Intern. Colloq. Autom. Lang. Program. (ICALP), number 3580 in Lecture Notes in Comput. Sci., pp. 1043–1050. Springer, 2005. [doi:10.1007/11523468_84]

[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, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. [doi:10.1137/S0097539705447372]

[15]   Subhash Khot and Ashok Kumar Ponnuswami: Better inapproximability results for maxclique, chromatic number and Min-3Lin-Deletion. In Proc. 33rd Intern. Colloq. Autom. Lang. Program. (ICALP), number 4051 in Lecture Notes in Comput. Sci., pp. 226–237. Springer, 2006. [doi:10.1007/11786986_21]

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

[17]   Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, and Nisheeth K. Vishnoi: On the optimality of a class of LP-based algorithms, 2009. [arXiv:0912.1776v1]

[18]   Elchanan Mossel: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In Proc. 49th FOCS, pp. 156–165. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.44]

[19]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: Invariance and optimality. Ann. of Math., 171(1):295–341, 2010. [doi:10.4007/annals.2010.171.295]

[20]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]

[21]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. In Proc. 38th STOC, pp. 11–20. ACM Press, 2006. [doi:10.1145/1132516.1132519]