{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:05Z","timestamp":1787323145301,"version":"3.56.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a Telov\u00fdchovy","doi-asserted-by":"publisher","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["249994"],"award-info":[{"award-number":["249994"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["263317"],"award-info":[{"award-number":["263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["17-20065S"],"award-info":[{"award-number":["17-20065S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-17314J"],"award-info":[{"award-number":["19-17314J"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Bir\u00f3, Hujter, and Tuza, who in 1992 introduced $H$-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi-)graph $H$. In this work, we turn to proper $H$-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph $H$ is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size $\\mathcal{O}(\\|H\\|^8)$, where $\\|H\\|$ is the size of graph $H$. In other words, we design an algorithm that for an $n$-vertex graph $G$ and integer $k\\geq 1$, in time polynomial in $n$ and $\\|H\\|$, outputs a graph $G'$ of size $\\mathcal{O}(\\|H\\|^8)$ and $k'\\leq |V(G')|$ such that the vertex set of $G$ is coverable by $k$ vertex-disjoint paths if and only if the vertex set of $G'$ is coverable by $k'$ vertex-disjoint paths. Hamiltonian Cycle admits a kernel of size $\\mathcal{O}(\\|H\\|^8)$. Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size $\\mathcal{O}(\\|H\\|^{10})$ into another \\sf NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in $n$ and $\\|H\\|$, outputs an equivalent instance of Prize Collecting Cycle Cover of size $\\mathcal{O}(\\|H\\|^{10})$. In all our algorithms we assume that a proper $H$-decomposition is given as a part of the input.<\/jats:p>","DOI":"10.1137\/19m1299001","type":"journal-article","created":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T12:57:01Z","timestamp":1619528221000},"page":"840-892","source":"Crossref","is-referenced-by-count":8,"title":["Kernelization of Graph Hamiltonicity: Proper $H$-Graphs"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3501-4608","authenticated-orcid":true,"given":"Steven","family":"Chaplick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":true,"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":true,"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0071-9149","authenticated-orcid":true,"given":"Peter","family":"Zeman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90078-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90646-W"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.006"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799357775"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , Discrete Math. Appl. 3, SIAM, Philadelphia, 1999,https:\/\/doi.org\/10.1137\/1.9780898719796.","DOI":"10.1137\/1.9780898719796"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21832"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-C"},{"key":"atypb11","first-page":"296","author":"Chaplick S.","year":"2019","journal-title":"Cham"},{"key":"atypb12","first-page":"167","author":"Chaplick S.","year":"2017","journal-title":"Cham"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2017.06.042"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00307-X"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb16","first-page":"150","author":"Cygan M.","year":"2011","journal-title":"IEEE"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90223-G"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, London, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.06.004"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9167-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00692-9"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi,\n                      Kernelization. Theory of Parameterized Preprocessing\n                      , Cambridge University Press, Cambridge, UK, 2019.","DOI":"10.1017\/9781107415157"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"atypb24","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-completeness\n                      , W. H. Freeman, San Francisco, CA, 1979."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, Elsevier Science B.V., Amsterdam, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2010.11.030"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.010"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90050-X"},{"key":"atypb31","first-page":"575","author":"Koutis I.","year":"2008","journal-title":"Berlin"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.04.045"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90025-S"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00057-4"},{"key":"atypb35","unstructured":"F. S. Roberts,\n                      Indifference graphs\n                      , in Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, MI, 1968), Academic Press, New York, 1969, pp. 139-146."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0221061"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1299001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:04Z","timestamp":1787319844000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1299001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1299001"],"URL":"https:\/\/doi.org\/10.1137\/19m1299001","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}