Kernelization of Graph Hamiltonicity: Proper H-Graphs

Abstract

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ó, 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.