{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:40:31Z","timestamp":1772372431719,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T00:00:00Z","timestamp":1536105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.438"],"award-info":[{"award-number":["639.021.438"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/501100000781","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"}]},{"name":"I-CORE","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-018-0512-8","type":"journal-article","created":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T15:19:17Z","timestamp":1536160757000},"page":"3993-4009","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["New Tools and Connections for Exponential-Time Approximation"],"prefix":"10.1007","volume":"81","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Parinya","family":"Chalermsook","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,5]]},"reference":[{"issue":"5","key":"512_CR1","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M Andrews","year":"2010","unstructured":"Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485\u2013520 (2010)","journal-title":"Combinatorica"},{"issue":"1","key":"512_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"512_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Guruganesh, G.: On the Lov\u00e1sz theta function for independent sets in sparse graphs. In: Symposium on Theory of Computing, STOC, pp. 193\u2013200 (2015)","DOI":"10.1145\/2746539.2746607"},{"issue":"3","key":"512_CR4","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability-towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"512_CR5","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"512_CR6","unstructured":"Bonnet, \u00c9., Lampis, M., Paschos, V.: Time-approximation trade-offs for inapproximable problems. In: Symposium on Theoretical Aspects of Computer Science, STACS, pp. 22:1\u201322:14 (2016)"},{"key":"512_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00236-016-0281-2","volume":"55","author":"\u00c9 Bonnet","year":"2016","unstructured":"Bonnet, \u00c9., Paschos, V.T.: Sparsification and subexponential approximation. Acta Inf. 55, 1\u201315 (2016)","journal-title":"Acta Inf."},{"issue":"17","key":"512_CR8","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954\u20131970 (2011)","journal-title":"Discret. Appl. Math."},{"key":"512_CR9","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Conference on Computational Complexity (CCC), pp. 252\u2013260 (2006)","DOI":"10.1109\/CCC.2006.6"},{"key":"512_CR10","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, L.: From gap-eth to fpt-inapproximability: Clique, dominating set, and more. In: Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 743\u2013754. IEEE (2017)","DOI":"10.1109\/FOCS.2017.74"},{"key":"512_CR11","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: Foundations of Computer Science, FOCS, pp. 370\u2013379 (2013)","DOI":"10.1109\/FOCS.2013.47"},{"issue":"3","key":"512_CR12","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2873054","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O.: Approximation resistance from pairwise-independent subgroups. J ACM 63(3), 27:1\u201327:32 (2016)","journal-title":"J ACM"},{"key":"512_CR13","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time approximation of hard problems (2008). arXiv:0810.4934"},{"issue":"16","key":"512_CR14","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16), 957\u2013961 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"40\u201342","key":"512_CR15","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40\u201342), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"512_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2004.12.017","volume":"94","author":"A Czumaj","year":"2005","unstructured":"Czumaj, A., Halld\u00f3rsson, M.M., Lingas, A., Nilsson, J.: Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Inf. Process. Lett. 94(2), 49\u201353 (2005)","journal-title":"Inf. Process. Lett."},{"key":"512_CR17","first-page":"128","volume":"23","author":"I Dinur","year":"2016","unstructured":"Dinur, I.: Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloq. Comput. Complex. (ECCC) 23, 128 (2016)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"issue":"2","key":"512_CR18","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2004","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219\u2013225 (2004)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"512_CR19","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"issue":"2","key":"512_CR20","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"512_CR21","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Salavatipour, M.R.: Approximability of packing disjoint cycles. In: International Symposium on Algorithms and Computation, pp. 304\u2013315. Springer (2007)","DOI":"10.1007\/978-3-540-77120-3_28"},{"issue":"5","key":"512_CR22","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"512_CR23","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$ n 1 - \u03f5 . In: 37th Annual Symposium on Foundations of Computer Science, FOCS, pp. 627\u2013636 (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"1","key":"512_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"J H\u00e5stad","year":"2005","unstructured":"H\u00e5stad, J., Khot, S.: Query efficient pcps with perfect completeness. Theor. Comput. 1(1), 119\u2013148 (2005). https:\/\/doi.org\/10.4086\/toc.2005.v001a007","journal-title":"Theor. Comput."},{"issue":"4","key":"512_CR25","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"512_CR26","first-page":"124","volume":"23","author":"S Khot","year":"2016","unstructured":"Khot, S., Minzer, D., Safra, M.: On independent sets, 2-to-2 games and grassmann graphs. Electron. Colloq. Comput. Complex. (ECCC) 23, 124 (2016)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"512_CR27","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: On independent sets, 2-to-2 games, and grassmann graphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 576\u2013589. ACM (2017)","DOI":"10.1145\/3055399.3055432"},{"key":"512_CR28","doi-asserted-by":"crossref","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxclique, chromatic number and Min-3Lin-deletion. In: Automata, Languages and Programming, International Colloquium, (ICALP), pp. 226\u2013237 (2006)","DOI":"10.1007\/11786986_21"},{"issue":"3","key":"512_CR29","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"512_CR30","doi-asserted-by":"publisher","unstructured":"Khot, S., Shinkar, I.: On hardness of approximating the parameterized clique problem. In: Innovations in Theoretical Computer Science (ITCS), pp. 37\u201345, New York, NY, USA. ACM (2016). https:\/\/doi.org\/10.1145\/2840728.2840733","DOI":"10.1145\/2840728.2840733"},{"key":"512_CR31","unstructured":"Laekhanukit, B.: Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, McGill University (2014)"},{"key":"512_CR32","unstructured":"Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense CSPs (2016). arXiv:1607.02986"},{"key":"512_CR33","unstructured":"Manurangsi, P., Trevisan, L.: Mildly exponential time approximation algorithms for vertex cover, balanced separator and uniform sparsest cut. In: Blais E., Jansen K., Rolim J.D.P., Steurer D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018 August 20\u201322, 2018, Princeton. Leibniz International Proceedings in Informatics, vol. 116, pp. 20:1\u201320:17. (2018)"},{"key":"512_CR34","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: Foundations of Computer Science (FOCS), pp. 338\u2013348 (2007)","DOI":"10.1109\/FOCS.2007.4389505"},{"issue":"5","key":"512_CR35","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/1754399.1754402","volume":"57","author":"D Moshkovitz","year":"2010","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. J. ACM 57(5), 29:1\u201329:29 (2010)","journal-title":"J. ACM"},{"issue":"2","key":"512_CR36","first-page":"415","volume":"026","author":"J Neetil","year":"1985","unstructured":"Neetil, J., Poljak, S.: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 026(2), 415\u2013419 (1985)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"512_CR37","doi-asserted-by":"publisher","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 21\u201323 May 2000, Portland, OR, USA, pp. 191\u2013199 (2000). https:\/\/doi.org\/10.1145\/335305.335329","DOI":"10.1145\/335305.335329"},{"key":"512_CR38","unstructured":"Williams, R., Yu, H.: Personal communication"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0512-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0512-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0512-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T22:00:39Z","timestamp":1751839239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0512-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,5]]},"references-count":38,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["512"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0512-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,5]]},"assertion":[{"value":"17 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}