{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:16Z","timestamp":1770994156662,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T00:00:00Z","timestamp":1666224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T00:00:00Z","timestamp":1666224000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation GA\u010cR","doi-asserted-by":"crossref","award":["#19-27871X"],"award-info":[{"award-number":["#19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation GA\u010cR","doi-asserted-by":"crossref","award":["#19-27871X"],"award-info":[{"award-number":["#19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Center for Foundations of Modern Computer Science","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00453-022-01052-5","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T09:02:41Z","timestamp":1666256561000},"page":"902-928","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Inapproximability of Independent Set in H-Free Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6838-1538","authenticated-orcid":false,"given":"Pavel","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[]},{"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[]},{"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,20]]},"reference":[{"issue":"1","key":"1052_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2003.09.003","volume":"135","author":"V Alekseev","year":"2004","unstructured":"Alekseev, V.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discret. Appl. Math. 135(1), 3\u201316 (2004). (Russian Translations II)","journal-title":"Discret. Appl. Math."},{"key":"1052_CR2","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pp. 3\u201313 (1982)"},{"issue":"1","key":"1052_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.4086\/toc.2011.v007a003","volume":"7","author":"P Austrin","year":"2011","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput. 7(1), 27\u201343 (2011)","journal-title":"Theory Comput."},{"issue":"3","key":"1052_CR4","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/15M1051002","volume":"47","author":"N Bansal","year":"2018","unstructured":"Bansal, N., Gupta, A., Guruganesh, G.: On the Lov\u00e1sz theta function for independent sets in sparse graphs. SIAM J. Comput. 47(3), 1039\u20131055 (2018)","journal-title":"SIAM J. Comput."},{"key":"1052_CR5","unstructured":"Bonnet, \u00c9.: private communication"},{"issue":"8","key":"1052_CR6","doi-asserted-by":"publisher","first-page":"2360","DOI":"10.1007\/s00453-020-00730-6","volume":"82","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in h-free graphs. Algorithmica 82(8), 2360\u20132394 (2020)","journal-title":"Algorithmica"},{"key":"1052_CR7","unstructured":"Bonnet, \u00c9., Bousquet, N., Thomass\u00e9, S., Watrigant, R.: When maximum stable set can be solved in FPT time. In: 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8\u201311, 2019, Shanghai University of Finance and Economics, Shanghai, China, pp. 49:1\u201349:22 (2019)"},{"key":"1052_CR8","unstructured":"Bonnet, \u00c9., Thomass\u00e9, S., Tran, X.\u00a0T., Watrigant, R.: An algorithmic weakening of the erd\u0151s-hajnal conjecture. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pp. 23:1\u201323:18. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"4","key":"1052_CR9","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1137\/18M1166869","volume":"49","author":"P Chalermsook","year":"2020","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, L.: From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more. SIAM J. Comput. 49(4), 772\u2013810 (2020)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1052_CR10","doi-asserted-by":"publisher","first-page":"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), 1\u201332 (2016)","journal-title":"J. ACM"},{"key":"1052_CR11","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected Steiner Network problems (2017)"},{"issue":"1","key":"1052_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1017\/S0004972700002872","volume":"33","author":"S Choudum","year":"1986","unstructured":"Choudum, S.: A simple proof of the Erd\u0151s\u2013Gallai theorem on graph sequences. Bull. Aust. Math. Soc. 33(1), 67\u201370 (1986)","journal-title":"Bull. Aust. Math. Soc."},{"key":"1052_CR13","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Pilipczuk, M., Pilipczuk, M., Thomass\u00e9, S.: Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 2260\u20132278 (2020)","DOI":"10.1137\/1.9781611975994.139"},{"issue":"3","key":"1052_CR14","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Burlingham, L.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"key":"1052_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"1052_CR16","doi-asserted-by":"crossref","unstructured":"Dabrowski, K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized algorithms for the independent set problem in some hereditary graph classes. In: Combinatorial Algorithms\u201421st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, pp. 1\u20139 (2010)","DOI":"10.1007\/978-3-642-19222-7_1"},{"key":"1052_CR17","unstructured":"Dinur, I., Manurangsi, P.: ETH-hardness of approximating 2-CSPs and Directed Steiner Network. In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pp. 36:1\u201336:20 (2018)"},{"key":"1052_CR18","unstructured":"Dinur, I., Manurangsi, P.: ETH-hardness of approximating 2-CSPs and Directed Steiner Network. CoRR, arXiv:1805.03867 (2018)"},{"key":"1052_CR19","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, P., Feldmann, A.\u00a0E., Rai, A., Rz\u0105\u017cewski, P.: Parameterized inapproximability of independent set in h-free graphs. In: Adler, I., M\u00fcller, H. (eds.) Graph-Theoretic Concepts in Computer Science\u201446th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pp. 40\u201353. Springer (2020)","DOI":"10.1007\/978-3-030-60440-0_4"},{"key":"1052_CR20","first-page":"49","volume-title":"A Combinatorial Problem in Geometry","author":"P Erd\u0151s","year":"1987","unstructured":"Erd\u0151s, P., Szekeres, G.: A Combinatorial Problem in Geometry, pp. 49\u201356. Birkh\u00e4user Boston, Boston (1987)"},{"issue":"2","key":"1052_CR21","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. Discrete Math. 18(2), 219\u2013225 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"1052_CR22","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":"6","key":"1052_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Lee, E., Manurangsi, P.: A survey on approximation in parameterized complexity: hardness and algorithms. Algorithms 13(6), 146 (2020)","journal-title":"Algorithms"},{"issue":"3","key":"1052_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"1052_CR25","doi-asserted-by":"crossref","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $$P_k$$-free graphs in quasi-polynomial time. In: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 613\u2013624 (2020)","DOI":"10.1109\/FOCS46700.2020.00063"},{"issue":"1","key":"1052_CR26","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0095-8956(75)90076-3","volume":"19","author":"D Geller","year":"1975","unstructured":"Geller, D., Stahl, S.: The chromatic number and other functions of the lexicographic product. J. Comb. Theory Ser. B 19(1), 87\u201395 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1052_CR27","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $$P_{6}$$-free graphs. ACM Trans. Algorithms 18(1), 4:1-4:57 (2022)","journal-title":"ACM Trans. Algorithms"},{"key":"1052_CR28","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California, USA, pp. 160\u2013169 (1995)"},{"key":"1052_CR29","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{{(1-\\epsilon )}}$$. In: Acta Mathematica, pp. 627\u2013636 (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"key":"1052_CR30","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer US (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1052_CR31","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for Max Clique, Chromatic Number and Min-3Lin-Deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) Automata, Languages and Programming, pp. 226\u2013237. Springer Berlin Heidelberg, Berlin (2006)"},{"key":"1052_CR32","doi-asserted-by":"crossref","unstructured":"Laekhanukit, B.: Parameters of two-prover-one-round game and the hardness of connectivity problems. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 1626\u20131643. SIAM (2014)","DOI":"10.1137\/1.9781611973402.118"},{"key":"1052_CR33","unstructured":"Lin, B., Ren, X., Sun, Y., Wang, X.: On lower bounds of approximating parameterized k-Clique. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), vol. 229, pp. 90:1\u201390:18 (2022)"},{"key":"1052_CR34","doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in $${P}_{5}$$-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"1052_CR35","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Zehavi, M.: Parameterized complexity and approximability of directed odd cycle transversal. In: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201920, pp. 2181-2200, USA. Society for Industrial and Applied Mathematics (2020)","DOI":"10.1137\/1.9781611975994.134"},{"issue":"4","key":"1052_CR36","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6(4), 595\u2013604 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"1052_CR37","unstructured":"Majewski, K., Masa\u0159\u00edk, T., Novotn\u00e1, J., Okrasa, K., Pilipczuk, M., Rz\u0105\u017cewski, P., Soko\u0142owski, M.: Max weight independent set in graphs with no long claws: An analog of the gy\u00e1rf\u00e1s\u2019 path argument. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pp. 93:1\u201393:19. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1052_CR38","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 62\u201381 (2020)","DOI":"10.1137\/1.9781611975994.5"},{"key":"1052_CR39","unstructured":"Manurangsi, P., Rubinstein, A., Schramm, T.: The Strongish planted clique hypothesis and its consequences. In: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 10:1\u201310:21 (2021)"},{"issue":"1","key":"1052_CR40","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."},{"issue":"2","key":"1052_CR41","doi-asserted-by":"publisher","first-page":"1:31","DOI":"10.1145\/3483425","volume":"18","author":"D Marx","year":"2022","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. ACM Trans. Algorithms 18(2), 1:31-13:64 (2022)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1052_CR42","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1052_CR43","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in $$P_t$$-free graphs via shrinking the space of induced paths. In: Le, H.V., King, V. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pp. 204\u2013209. SIAM (2021)","DOI":"10.1137\/1.9781611976472.23"},{"key":"1052_CR44","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"1","key":"1052_CR45","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalite maximum dans un graphe sans etoile. Discret. Math. 29(1), 53\u201376 (1980)","journal-title":"Discret. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01052-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01052-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01052-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T06:54:07Z","timestamp":1728197647000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01052-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,20]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1052"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01052-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,20]]},"assertion":[{"value":"2 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Pavel Dvo\u0159\u00e1k is now a visiting fellow at School of Technology and Computer Science, Tata Institute of Fundamental Research where Praladh Harsha, member of the editorial board, is a faculty. Other coauthors have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}