{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:56Z","timestamp":1781031416111,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":86,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Research Council of Norway","award":["314528"],"award-info":[{"award-number":["314528"]}]},{"name":"Research Council of Norway","award":["355137"],"award-info":[{"award-number":["355137"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101199930"],"award-info":[{"award-number":["101199930"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Charles University Grant Agency","award":["370122"],"award-info":[{"award-number":["370122"]}]},{"name":"Charles University Research Centre","award":["UNCE\/24\/SCI\/02"],"award-info":[{"award-number":["UNCE\/24\/SCI\/02"]}]},{"name":"Charles University Grant Agency","award":["PRIMUS\/24\/SCI\/008"],"award-info":[{"award-number":["PRIMUS\/24\/SCI\/008"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800747","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"276-285","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6386","authenticated-orcid":false,"given":"Nikola","family":"Jedli\u010dkov\u00e1","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2620-6133","authenticated-orcid":false,"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3327-9768","authenticated-orcid":false,"given":"Danil","family":"Sagunov","sequence":"additional","affiliation":[{"name":"St. Petersburg State University, St. Petersburg, Russian Federation"},{"name":"St. Petersburg Department of V.A.Steklov Mathematical Institute of the Russian Academy of Sciences, St. Petersburg, Russian Federation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9436-7310","authenticated-orcid":false,"given":"Kirill","family":"Simonov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.44"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73367-X"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M140482X"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90023-3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90063-5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90135-3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2073-3"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1148566"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.139"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_17"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261316"},{"key":"e_1_3_2_1_15_1","volume-title":"Handbook of combinatorics","author":"Bondy J. A.","unstructured":"J. A. Bondy. 1995. Basic graph theory: paths and circuits. In Handbook of combinatorics, Vol. 1, 2. Elsevier Sci. B. V., Amsterdam, 3\u2013110."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1239\u20131256","author":"Chudnovsky Maria","year":"2019","unstructured":"Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong. 2019. Four-coloring P_6-free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1239\u20131256."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90079-9"},{"key":"e_1_3_2_1_20_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"54","author":"Crowston Robert","year":"2013","unstructured":"Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. 2013. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 24). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 43\u201354."},{"key":"e_1_3_2_1_21_1","volume-title":"Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh.","author":"Cygan Marek","year":"2015","unstructured":"Marek Cygan, Fedor V. Fomin, \u0141 ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. isbn:978-3-319-21274-6"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488646"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCTB.2023.10.006"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90059-8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90223-G"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00571188"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"e_1_3_2_1_29_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R. Fellows. 1999. Parameterized complexity. Springer-Verlag, New York."},{"key":"e_1_3_2_1_30_1","volume-title":"I4th Int. Conf. on the Theory and Applications of Graphs","author":"Duffus D.","year":"1980","unstructured":"D. Duffus, R.J. Gould, and M.S. Jacobson. 1981. Forbidden subgraphs and the Hamiltonian theme. In I4th Int. Conf. on the Theory and Applications of Graphs, Kalamazoo, 1980. 297\u2013316."},{"key":"e_1_3_2_1_31_1","unstructured":"Fedor V. Fomin Petr A. Golovach Nikola Jedli\u010dkov\u00e1 Jan Kratochv\u00edl Danil Sagunov and Kirill Simonov. 2026. Path Cover Hamiltonicity and Independence Number: An FPT Perspective. arxiv:2403.05943. arxiv:2403.05943"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch142"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460956"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/080742270"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3280824"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.20"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1558008"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3768573"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384318"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Jacob Fox and Benny Sudakov. 2009. Paths and Stability Number in Digraphs. The Electronic Journal of Combinatorics N23\u2013N23.","DOI":"10.37236\/261"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.002"},{"key":"e_1_3_2_1_43_1","first-page":"181","article-title":"Verallgemeinerung eines graphentheoretischen Satzes von R\u00e9dei. Acta Sci","volume":"21","author":"Gallai T.","year":"1960","unstructured":"T. Gallai and A. N. Milgram. 1960. Verallgemeinerung eines graphentheoretischen Satzes von R\u00e9dei. Acta Sci. Math. (Szeged), 21 (1960), 181\u2013186. issn:0001-6969","journal-title":"Math. (Szeged)"},{"key":"e_1_3_2_1_44_1","unstructured":"Luyining Gan Jie Han and Jie Hu. 2023. An algorithmic version of the Hajnal\u2013Szemer\u00e9di theorem. arxiv:2307.08056."},{"key":"e_1_3_2_1_45_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. isbn:0-7167-1044-7"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch80"},{"key":"e_1_3_2_1_48_1","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin Charles","unstructured":"Martin Charles Golumbic. 2004. Algorithmic graph theory and perfect graphs. Elsevier."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993700"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9262-y"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2207.12278"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/140980946"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1330-6"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.01.004"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90210-9"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90001-3"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90130-A"},{"key":"e_1_3_2_1_58_1","volume-title":"Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (Lecture Notes in Computer Science","volume":"39","author":"Jansen Bart M. P.","year":"2019","unstructured":"Bart M. P. Jansen, L\u00e1szl\u00f3 Kozma, and Jesper Nederlof. 2019. Hamiltonicity Below Dirac\u2019s Condition. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (Lecture Notes in Computer Science, Vol. 11789). Springer, 27\u201339."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-63021-7_14"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.6"},{"key":"e_1_3_2_1_61_1","volume-title":"Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO) (Lecture Notes in Comput. Sci.","volume":"384","year":"2008","unstructured":"Ken-ichi Kawarabayashi. 2008. An Improved Algorithm for Finding Cycles Through Elements. In Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO) (Lecture Notes in Comput. Sci., Vol. 5035). Springer, 374\u2013384."},{"key":"e_1_3_2_1_62_1","volume-title":"A survey on Hamiltonian cycles. Interdisciplinary information sciences, 7, 1","year":"2001","unstructured":"Ken-ichi Kawarabayashi. 2001. A survey on Hamiltonian cycles. Interdisciplinary information sciences, 7, 1 (2001), 25\u201339."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90050-X"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1023"},{"key":"e_1_3_2_1_65_1","volume-title":"Graphok \u00e9s matrixok. Matematikai \u00e9s Fizikai Lapok, 38","author":"K\u0151nig D\u00e9nes","year":"1931","unstructured":"D\u00e9nes K\u0151nig. 1931. Graphok \u00e9s matrixok. Matematikai \u00e9s Fizikai Lapok, 38 (1931), 116\u2013119. K\u0151nig\u2019s theorem on bipartite matchings and vertex covers"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.90"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2020.47"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2018.135"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2023.28"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.08.004"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01093-w"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2014.04.011"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00057-4"},{"key":"e_1_3_2_1_78_1","volume-title":"Studies in Pure Mathematics (Presented to Richard Rado)","author":"John Alvah Nash-Williams Crispin St","unstructured":"Crispin St John Alvah Nash-Williams. 1971. Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. In Studies in Pure Mathematics (Presented to Richard Rado). Academic Press, London-New York, 157\u2013183."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00048-8"},{"key":"e_1_3_2_1_80_1","first-page":"39","article-title":"Ein kombinatorischer Satz. Acta Litterarum ac Scientiarum","volume":"7","author":"R\u00e9dei L\u00e1szl\u00f3","year":"1934","unstructured":"L\u00e1szl\u00f3 R\u00e9dei. 1934. Ein kombinatorischer Satz. Acta Litterarum ac Scientiarum, Szeged, 7 (1934), 39\u201343.","journal-title":"Szeged"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.02.013"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2055"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2013.341"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.02.005"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:05Z","timestamp":1781027885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":86,"alternative-id":["10.1145\/3798129.3800747","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800747","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}