Improved Inapproximability Results for Maximum $k$-Colorable Subgraph

by Venkatesan Guruswami and Ali Kemal Sinop

Theory of Computing, Volume 9(11), pp. 413-435, 2013

Bibliography with links to cited articles

[1]   Per Austrin, Ryan O’Donnell, Li-Yang Tan, and John Wright: New NP-hardness results for 3-coloring and 2-to-1 label cover. Technical report, 2012. Preliminary version in APPROX’12. [arXiv:1210.5648]

[2]   Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan: On weighted vs unweighted versions of combinatorial optimization problems. Inform. and Comput., 167(1):10–26, 2001. Preliminary version in 4th ISTCS, 1996. [doi:10.1006/inco.2000.3011]

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

[4]   Alan M. Frieze and Mark Jerrum: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 1997. Preliminary version in IPCO’95. [doi:10.1007/BF02523688]

[5]   Venkatesan Guruswami: Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Algorithmica, 38(3):451–469, 2004. Preliminary version in APPROX’00. [doi:10.1007/s00453-003-1072-z]

[6]   Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, and Luca Trevisan: A tight characterization of NP with 3 query PCPs. In Proc. 39th FOCS, pp. 8–17. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743424]

[7]   Venkatesan Guruswami and Ali Kemal Sinop: Improved inapproximability results for maximum k-colorable subgraph. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 163–176. Springer, 2009. [doi:10.1007/978-3-642-03685-9_13]

[8]   Johan HÃ¥stad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[9]   Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi: On the hardness of approximating MAX k-CUT and its dual. Chicago J. Theor. Comput. Sci., 1997(2), 1997. CJTCS. Preliminary version in ISTCS’96.

[10]   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]

[11]   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. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372]

[12]   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. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[13]   Ryan O’Donnell and Yi Wu: Conditional hardness for satisfiable 3-CSPs. In Proc. 41st STOC, pp. 493–502. ACM Press, 2009. [doi:10.1145/1536414.1536482]

[14]   Christos H. Papadimitriou and Mihalis Yannakakis: Optimization, approximation, and complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-0000(91)90023-X]

[15]   Erez Petrank: The hardness of approximation: Gap location. Comput. Complexity, 4(2):133–157, 1994. Preliminary version in ISTCS’93. [doi:10.1007/BF01202286]

[16]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

[17]   Alistair Sinclair: Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput., 1(4):351–370, 1992. Preliminary version in LATIN’92. [doi:10.1017/S0963548300000390]