{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T12:14:02Z","timestamp":1790252042745,"version":"4.1.0"},"reference-count":85,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["2015-04659"],"award-info":[{"award-number":["2015-04659"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["No 677651"],"award-info":[{"award-number":["No 677651"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["621\/12"],"award-info":[{"award-number":["621\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218620"],"award-info":[{"award-number":["1218620"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1540547"],"award-info":[{"award-number":["1540547"]}],"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 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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1740425"],"award-info":[{"award-number":["CCF 1740425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique $({\\sf Clique})$ and Minimum Dominating Set $({\\sf DomSet})$ problems parameterized by the size of the optimal solution. In particular, letting ${\\sf OPT}$ be the optimum and $N$ be the size of the input, is there an algorithm that runs in $t({\\sf OPT}){\\operatorname{poly}}(N)$ time and outputs a solution of size $f({\\sf OPT})$ for any computable functions $t$ and $f$ that are independent of $N$ (for ${\\sf Clique}$, we want $f({\\sf OPT})=\\omega(1)$)? In this paper, we show that both ${\\sf Clique}$ and ${\\sf DomSet}$ admit no nontrivial FPT-approximation algorithm, i.e., there is no $o({\\sf OPT})$-FPT-approximation algorithm for ${\\sf Clique}$ and no $f({\\sf OPT})$-FPT-approximation algorithm for ${\\sf DomSet}$ for any function $f$. In fact, our results imply something even stronger: The best way to solve ${\\sf Clique}$ and ${\\sf DomSet}$, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable 3 \\sf SAT formula and one which is not even $(1 - \\varepsilon)$-satisfiable for some constant $\\varepsilon &gt; 0$. Besides ${\\sf Clique}$ and ${\\sf DomSet}$, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the $k^{o(1)}$-FPT-approximation algorithm for the Densest $k$-Subgraph problem.<\/jats:p>","DOI":"10.1137\/18m1166869","type":"journal-article","created":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T10:26:22Z","timestamp":1595327182000},"page":"772-810","source":"Crossref","is-referenced-by-count":23,"title":["From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More"],"prefix":"10.1137","volume":"49","author":[{"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4476-8914","authenticated-orcid":true,"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4468-2675","authenticated-orcid":true,"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,7,21]]},"reference":[{"key":"atypb1","first-page":"44","author":"Aaronson S.","year":"2014","journal-title":"NJ"},{"key":"atypb2","first-page":"25","author":"Abboud A.","year":"2017","journal-title":"NJ"},{"key":"atypb3","first-page":"689","author":"Allen S. R.","year":"2015","journal-title":"NJ"},{"key":"atypb5","first-page":"836","author":"Applebaum B.","year":"2017","journal-title":"NJ"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"atypb9","first-page":"294","author":"Bellare M.","year":"1993","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan,\n                      Improved non-approximability results\n                      , in STOC, 1994, ACM, New York, pp. 184-193.","DOI":"10.1145\/195058.195129"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90056-L"},{"key":"atypb12","first-page":"10","volume":"6","author":"Bhangale A.","year":"2016","journal-title":"Germany"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan,\n                      Detecting high log-densities: an $O(n^{1\/4})$ approximation for densest $k$-subgraph\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, MA, ACM, New York, 2010, pp. 201-210,https:\/\/doi.org\/10.1145\/1806689.1806719.","DOI":"10.1145\/1806689.1806719"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"A. Bhaskara, M. Charikar, A. Vijayaraghavan, V. Guruswami, and Y. Zhou,\n                      Polynomial integrality gaps for strong SDP relaxations of densest $k$-subgraph\n                      , in Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, Philadelphia, 2012, SIAM, Philadelphia, pp. 388-405,http:\/\/dl.acm.org\/citation.cfm?id=2095116.2095150.","DOI":"10.1137\/1.9781611973099.34"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"atypb16","first-page":"22","author":"Bonnet \u00c9.","year":"2016","journal-title":"Germany"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Braverman, Y. Kun-Ko, A. Rubinstein, and O. Weinstein,\n                      \n                        ETH hardness for densest-\n                        k\n                        -subgraph with perfect completeness\n                      \n                      , in SODA, 2017, SIAM, Philadelphia, pp. 1326-1341.","DOI":"10.1137\/1.9781611974782.86"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90275-F"},{"key":"atypb19","first-page":"1557","author":"Chalermsook P.","year":"2013","journal-title":"New York"},{"key":"atypb20","first-page":"370","author":"Chalermsook P.","year":"2013","journal-title":"NJ"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9464-3"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. Chen, X. Huang, I. A. Kanj, and G. Xia,\n                      Linear FPT reductions and computational lower bounds\n                      , in STOC, 2004, ACM, New York, pp. 212-221.","DOI":"10.1145\/1007352.1007391"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7137-6"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"atypb25","first-page":"109","author":"Chen Y.","year":"2006","journal-title":"Berlin"},{"key":"atypb26","unstructured":"Y. Chen, M. Grohe, and M. Gr\u00fcber,\n                      On parameterized approximability\n                      , Electronic Colloquium on Computational Complexity (ECCC), TR07-106, 2007,http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-106\/index.html."},{"key":"atypb27","first-page":"505","author":"Chen Y.","year":"2016","journal-title":"NJ"},{"key":"atypb28","first-page":"110","author":"Chitnis R. H.","year":"2013","journal-title":"Switzerland"},{"key":"atypb29","first-page":"900","author":"Chlamt\u00e1\u010d E.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"atypb32","unstructured":"I. Dinur,\n                      Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover\n                      , ECCC, TR16-128, 2016."},{"key":"atypb33","first-page":"624","volume":"2014","author":"Dinur I.","year":"2014","journal-title":"STOC"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Springer, London, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.017"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.05.001"},{"key":"atypb37","first-page":"1210","author":"Elbassioni K.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb38","first-page":"2","author":"Engebretsen L.","year":"2000","journal-title":"Berlin"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb40","first-page":"534","author":"Feige U.","year":"2002","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325375"},{"key":"atypb44","unstructured":"U. Feige and S. Kogan,\n                      The Hardness of Approximating Hereditary Properties\n                      , Technical report, Weizmann Institute, Rehovot, Israel, 2005."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"atypb46","first-page":"26","volume":"2","author":"Fellows M. R.","year":"2012","journal-title":"Dagstuhl Rep."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"atypb48","first-page":"363","author":"Grohe M.","year":"2007","journal-title":"Berlin"},{"key":"atypb49","unstructured":"M. T. Hajiaghayi, R. Khandekar, and G. Kortsarz,\n                      Fixed Parameter Inapproximability for Clique and Set Cover in Time Super-exponential in OPT\n                      , preprint, arXiv:1310.2711, 2013."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"J. H\\aastad,\n                      Clique is hard to approximate within $n^{1-\\epsilon}$\n                      , in 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, 1996, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 627-636,https:\/\/doi.org\/10.1109\/SFCS.1996.548522.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb55","unstructured":"Karthik C. S., B. Laekhanukit, and P. Manurangsi,\n                      On the Parameterized Complexity of Approximating Dominating Set\n                      , preprint, arXiv:\/1711.11029, 2017."},{"key":"atypb56","unstructured":"N. Kayal,\n                      Solvability of systems of polynomial equations over finite fields\n                      ,https:\/\/simons.berkeley.edu\/talks\/neeraj-kayal-2014-10-13(2014)."},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      Improved inaproximability results for maxclique, chromatic number and approximate graph coloring\n                      , in 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, NV, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 600-609,https:\/\/doi.org\/10.1109\/SFCS.2001.959936.","DOI":"10.1109\/SFCS.2001.959936"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"atypb59","first-page":"226","author":"Khot S.","year":"2006","journal-title":"Berlin"},{"key":"atypb60","first-page":"137","author":"Khot S.","year":"2000","journal-title":"Berlin"},{"key":"atypb61","first-page":"37","author":"Khot S.","year":"2016","journal-title":"New York"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"atypb63","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and D. Peleg,\n                      On choosing a dense subgraph (extended abstract)\n                      , in 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, IEEE Computer Society, Los Alamitos, CA, pp. 692-701.","DOI":"10.1109\/SFCS.1993.366818"},{"key":"atypb64","doi-asserted-by":"crossref","unstructured":"J. R. Lee, P. Raghavendra, and D. Steurer,\n                      Lower bounds on the size of semidefinite programming relaxations\n                      , in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, Portland, OR, ACM, New York, 2015, pp. 567-576,https:\/\/doi.org\/10.1145\/2746539.2746599.","DOI":"10.1145\/2746539.2746599"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"atypb66","first-page":"605","author":"Lin B.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb67","first-page":"40","author":"Lund C.","year":"1993","journal-title":"Berlin"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"atypb69","unstructured":"P. Manurangsi,\n                      On Approximating Projection Games\n                      , Master's thesis, MIT, Cambridge, MA, 2015."},{"key":"atypb70","first-page":"954","author":"Manurangsi P.","year":"2017","journal-title":"New York"},{"key":"atypb71","unstructured":"P. Manurangsi,\n                      Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis\n                      , in 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstahl, Wadern, Germany, 2017, 79,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.79."},{"key":"atypb72","unstructured":"P. Manurangsi and P. Raghavendra,\n                      A birthday repetition theorem and complexity of approximating dense CSPs\n                      , ICALP (2017), 78."},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.09.001"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.011"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"atypb77","first-page":"1065","author":"P\u01cetrascu M.","year":"2010","journal-title":"New York"},{"key":"atypb78","first-page":"245","author":"Raghavendra P.","year":"2008","journal-title":"New York"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"atypb80","doi-asserted-by":"crossref","unstructured":"G. Schoenebeck,\n                      Linear level lasserre lower bounds for certain k-CSPs\n                      , in 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 593-602,https:\/\/doi.org\/10.1109\/FOCS.2008.74.","DOI":"10.1109\/FOCS.2008.74"},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"atypb82","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"atypb83","doi-asserted-by":"crossref","unstructured":"D. P. Williamson and D. B. Shmoys,\n                      The Design of Approximation Algorithms\n                      , Cambridge University Press, New York, 2011.","DOI":"10.1017\/CBO9780511921735"},{"key":"atypb84","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"},{"key":"atypb85","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940870"},{"key":"atypb86","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1166869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:05Z","timestamp":1787336705000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1166869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":85,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1166869"],"URL":"https:\/\/doi.org\/10.1137\/18m1166869","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}