Completion to Chordal Distance-Hereditary Graphs: A Quartic Vertex-Kernel

Abstract

Given a class of graphs $\mathcal {G}$ and a graph $G = (V,E)$, the aim of the $\mathcal {G}$ -completion problem is to find a set of at most k non-edges whose addition in G results in a graph that belongs to $\mathcal {G}$. Completion to chordal or to natural subclasses of chordal graphs cover a broad range of classical NP-Complete problems, that have been extensively studied. When $\mathcal {G}$ coincides with the class of chordal graphs, the problem is the well-known Minimum Fill-In problem. Other notable examples include completion to proper interval, threshold or trivially perfect graphs. Aforementioned problems are known to admit polynomial kernels, and it has been conjectured that completion to subclasses of chordal graphs further characterized by a finite number of forbidden induced subgraphs admits polynomial kernels. We investigate this line of research by considering completion to an important subclass of chordal graphs, namely chordal distance-hereditary graphs. Chordal distance-hereditary graphs are a natural generalization of trivially perfect graphs and have been extensively studied from the structural viewpoint. However, to the best of our knowledge, completion to chordal distance-hereditary graphs has not received attention so far. We thus initiate the first algorithmic study of this problem, and prove its NP-Completeness and that it admits a kernel with $O(k^4)$ vertices. To that aim, we rely on several known characterizations of chordal distance-hereditary graphs. In particular, such graphs admit a tree-like decomposition, so-called clique laminar tree. Unlike all aforementioned subclasses of chordal graphs, this decomposition does not correspond to a partition of the vertex set at hand. To circumvent this, we propose an approach based on the notion of clique (minimal) separator decomposition and a new characterization of chordal distance-hereditary graphs that might be of independent interest.