{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:11:28Z","timestamp":1788570688413,"version":"build-2803163510"},"reference-count":61,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2018,1,17]],"date-time":"2018-01-17T00:00:00Z","timestamp":1516147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1540685"],"award-info":[{"award-number":["CCF 1540685"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1655215"],"award-info":[{"award-number":["CCF 1655215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Small Set Expansion Hypothesis is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose (edge) expansion is almost zero and one in which all small subsets of vertices have expansion almost one. In this work, we prove conditional inapproximability results with essentially optimal ratios for the following graph problems based on this hypothesis: Maximum Edge Biclique, Maximum Balanced Biclique, Minimum k-Cut and Densest At-Least-k-Subgraph. Our hardness results for the two biclique problems are proved by combining a technique developed by Raghavendra, Steurer and Tulsiani to avoid locality of gadget reductions with a generalization of Bansal and Khot\u2019s long code test whereas our results for Minimum k-Cut and Densest At-Least-k-Subgraph are shown via elementary reductions.<\/jats:p>","DOI":"10.3390\/a11010010","type":"journal-article","created":{"date-parts":[[2018,1,17]],"date-time":"2018-01-17T12:17:11Z","timestamp":1516191431000},"page":"10","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":46,"title":["Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis"],"prefix":"10.3390","volume":"11","author":[{"given":"Pasin","family":"Manurangsi","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94709, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,1,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","article-title":"Proof Verification and the Hardness of Approximation Problems","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","article-title":"Probabilistic Checking of Proofs: A New Characterization of NP","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","article-title":"Some Optimal Inapproximability Results","volume":"48","year":"2001","journal-title":"J. ACM"},{"key":"ref_4","unstructured":"H\u00e5stad, J. (1996). Clique is Hard to Approximate within n1\u2212\u03b5, Springer."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"221","DOI":"10.4086\/toc.2015.v011a007","article-title":"The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover","volume":"11","author":"Moshkovitz","year":"2015","journal-title":"Theory Comput."},{"key":"ref_6","unstructured":"Dinur, I., and Steurer, D. (June, January 31). Analytical approach to parallel repetition. Proceedings of the STOC \u201914, Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Khot, S. (2002, January 19\u201321). On the Power of Unique 2-prover 1-round Games. Proceedings of the STOC \u201902, Thiry-Fourth Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/510014.510017"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","article-title":"Vertex cover might be hard to approximate to within 2 \u2212 \u03b5","volume":"74","author":"Khot","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","article-title":"Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?","volume":"37","author":"Khot","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., and Steurer, D. (2010, January 5\u20138). Graph Expansion and the Unique Games Conjecture. Proceedings of the STOC \u201910, Forty-Second ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806792"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., and Tulsiani, M. (2012, January 26\u201329). Reductions Between Expansion Problems. Proceedings of the CCC \u201912, 27th Conference on Computational Complexity, Porto, Portugal.","DOI":"10.1109\/CCC.2012.43"},{"key":"ref_12","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","article-title":"The NP-completeness Column: An Ongoing Guide","volume":"8","author":"Johnson","year":"1987","journal-title":"J. Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","article-title":"The Maximum Edge Biclique Problem is NP-complete","volume":"131","author":"Peeters","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Khot, S. (2001, January 14\u201317). Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/SFCS.2001.959936"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Khot, S., and Ponnuswami, A.K. (2006, January 10\u201314). Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. Proceedings of the International Colloquium on Automata, Languages, and Programming, Venice, Italy.","DOI":"10.1007\/11786986_21"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","article-title":"Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number","volume":"3","author":"Zuckerman","year":"2007","journal-title":"Theory Comput."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Feige, U. (2002, January 19\u201321). Relations Between Average Case Complexity and Approximation Complexity. Proceedings of the STOC \u201902, Thiry-Fourth Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/509984.509985"},{"key":"ref_19","unstructured":"Feige, U., and Kogan, S. (2004). Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem, Weizmann Institute of Science. Technical Report."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1137\/S0097539705447037","article-title":"Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique","volume":"36","author":"Khot","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1137\/080729256","article-title":"Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut","volume":"40","author":"Mastrolilli","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2626","DOI":"10.1137\/16M1082421","article-title":"Bicovering: Covering Edges With Two Small Subsets of Vertices","volume":"31","author":"Bhangale","year":"2016","journal-title":"SIAM J. Discrete Math."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Manurangsi, P. (2017, January 19\u201323). Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph. Proceedings of the STOC \u201917, 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/3055399.3055412"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which Problems Have Strongly Exponential Complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_25","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover","volume":"23","author":"Dinur","year":"2016","journal-title":"ECCC Electron. Colloq. Comput. Complex."},{"key":"ref_26","unstructured":"Manurangsi, P., and Raghavendra, P. (2017, January 10\u201314). A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. Proceedings of the ICALP \u201917, 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1002\/rsa.3240030402","article-title":"Large Cliques Elude the Metropolis Process","volume":"3","author":"Jerrum","year":"1992","journal-title":"Random Struct. Algorithms"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","article-title":"Expected Complexity of Graph Partitioning Problems","volume":"57","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","article-title":"On the Complexity of Approximating the Independent Set Problem","volume":"96","author":"Berman","year":"1992","journal-title":"Inf. Comput."},{"key":"ref_30","unstructured":"Blum, A. (1991). Algorithms for Approximate Graph Coloring. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","article-title":"A polynomial algorithm for the k-cut problem for fixed k","volume":"19","author":"Goldschmidt","year":"1994","journal-title":"Math. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","article-title":"Finding k Cuts Within Twice the Optimal","volume":"24","author":"Saran","year":"1995","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"Naor, J.S., and Rabani, Y. (2001, January 7\u20139). Tree Packing and Approximating k-cuts. Proceedings of the SODA \u201901, Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1023\/A:1011620607786","article-title":"Approximating the minimum k-way cut in a graph via minimum 3-way cuts","volume":"5","author":"Zhao","year":"2001","journal-title":"J. Comb. Optim."},{"key":"ref_35","unstructured":"Ravi, R., and Sinha, A. (2002, January 6\u20138). Approximating k-cuts via Network Strength. Proceedings of the SODA \u201902, Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1007\/s00453-009-9316-1","article-title":"Tight approximation ratio of a general greedy splitting algorithm for the minimum k-way cut problem","volume":"59","author":"Xiao","year":"2011","journal-title":"Algorithmica"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., and Li, J. (arXiv, 2018). An FPT Algorithm Beating 2-Approximation for k-Cut, arXiv.","DOI":"10.1137\/1.9781611975031.179"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Andersen, R., and Chellapilla, K. (2009, January 12\u201313). Finding Dense Subgraphs with Size Bounds. Proceedings of the International Workshop on Algorithms and Models for the Web-Graph 2009, Barcelona, Spain.","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"ref_39","unstructured":"Andersen, R. (arXiv, 2007). Finding large and small dense subgraphs, arXiv."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Khuller, S., and Saha, B. (2009, January 5\u201312). On Finding Dense Subgraphs. Proceedings of the International Colloquium on Automata, Languages, and Programming, Rhodes, Greece.","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"ref_41","unstructured":"Bergner, L. (2013). Small Set Expansion. [Master\u2019s Thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne]."},{"key":"ref_42","unstructured":"Kortsarz, G., and Peleg, D. (1993, January 3\u20135). On Choosing a Dense Subgraph (Extended Abstract). Proceedings of the 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, USA."},{"key":"ref_43","unstructured":"Feige, U., and Seltser, M. (1997). On the Densest k-Subgraph Problem, Weizmann Institute of Science. Technical Report."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Srivastav, A., and Wolf, K. (1998, January 18\u201319). Finding Dense Subgraphs with Semidefinite Programming. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, Aalborg, Denmark.","DOI":"10.1007\/BFb0053974"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.2001.1183","article-title":"Approximation Algorithms for Maximization Problems Arising in Graph Partitioning","volume":"41","author":"Feige","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","article-title":"The Dense k-Subgraph Problem","volume":"29","author":"Feige","year":"2001","journal-title":"Algorithmica"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","article-title":"Complexity of finding dense subgraphs","volume":"121","author":"Asahiro","year":"2002","journal-title":"Discrete Appl. Math."},{"key":"ref_48","unstructured":"Goldstein, D., and Langberg, M. (arXiv, 2009). The Dense k Subgraph problem, arXiv."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., and Vijayaraghavan, A. (2010, January 5\u20138). Detecting high log-densities: An O(n1\/4) approximation for densest k-subgraph. Proceedings of the STOC \u201910, 42nd ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806719"},{"key":"ref_50","unstructured":"Alon, N., Arora, S., Manokaran, R., Moshkovitz, D., and Weinstein, O. (2018). Inapproximabilty of Densest k-Subgraph from Average Case Hardness, Unpublished Manuscript."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., and Zhou, Y. (2012, January 17\u201319). Polynomial Integrality Gaps for Strong SDP Relaxations of Densest k-subgraph. Proceedings of the SODA \u201912, Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.34"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Braverman, M., Ko, Y.K., Rubinstein, A., and Weinstein, O. (2017, January 16\u201319). ETH Hardness for Densest-k-Subgraph with Perfect Completeness. Proceedings of the SODA \u201917, Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.86"},{"key":"ref_53","unstructured":"Manurangsi, P. (2015). On Approximating Projection Games. [Master\u2019s Thesis, Massachusetts Institute of Technology]."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Chlamt\u00e1c, E., Manurangsi, P., Moshkovitz, D., and Vijayaraghavan, A. (2017, January 16\u201319). Approximation Algorithms for Label Cover and The Log-Density Threshold. Proceedings of the SODA \u201917, Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.57"},{"key":"ref_55","unstructured":"O\u2019Donnell, R. (2014). Analysis of Boolean Functions, Cambridge University Press."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"295","DOI":"10.4007\/annals.2010.171.295","article-title":"Noise stability of functions with low influences: Invariance and optimality","volume":"171","author":"Mossel","year":"2010","journal-title":"Ann. Math."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"759","DOI":"10.4086\/toc.2013.v009a024","article-title":"Hardness of Vertex Deletion and Project Scheduling","volume":"9","author":"Svensson","year":"2013","journal-title":"Theory Comput."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Bansal, N., and Khot, S. (2009, January 5\u201327). Optimal Long Code Test with One Free Bit. Proceedings of the FOCS \u201909, 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, USA.","DOI":"10.1109\/FOCS.2009.23"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Louis, A., Raghavendra, P., and Vempala, S. (2013, January 26\u201329). The Complexity of Approximating Vertex Expansion. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.46"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/972639.972644","article-title":"Segmentation Problems","volume":"51","author":"Kleinberg","year":"2004","journal-title":"J. ACM"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/BF01277956","article-title":"Derandomized Graph Products","volume":"5","author":"Alon","year":"1995","journal-title":"Comput. Complex."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/1\/10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:51:40Z","timestamp":1760194300000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,17]]},"references-count":61,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2018,1]]}},"alternative-id":["a11010010"],"URL":"https:\/\/doi.org\/10.3390\/a11010010","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,17]]}}}