Show simple item record

dc.contributor.authorChaplick, Steven
dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorKnop, Dusan
dc.contributor.authorZeman, Peter
dc.date.accessioned2022-01-31T13:37:45Z
dc.date.available2022-01-31T13:37:45Z
dc.date.created2022-01-06T10:34:36Z
dc.date.issued2021
dc.identifier.issn0895-4801
dc.identifier.urihttps://hdl.handle.net/11250/2976040
dc.description.abstractWe 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ó, 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.en_US
dc.language.isoengen_US
dc.publisherSIAMen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleKernelization of Graph Hamiltonicity: Proper H-Graphsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2021 SIAMen_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doihttps://doi.org/10.1137/19M1299001
dc.identifier.cristin1975694
dc.source.journalSIAM Journal on Discrete Mathematicsen_US
dc.source.pagenumber840-892en_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationSIAM Journal on Discrete Mathematics. 2021, 35 (2), 840-892.en_US
dc.source.volume35en_US
dc.source.issue2en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal