Connected Dominating Set on Semi-Ladder-Free Graphs
En palabras de los autores
We study \textsc{Connected Dominating Set} on graphs whose closed-neighborhood set systems are -semi-ladder-free. This structural condition strictly generalizes the biclique-free setting and provides a natural regime for connectivity-constrained domination. We obtain both a fixed-parameter algorithm and an approximate kernelization framework for the problem on this class. Our algorithmic result is based on a new compact representation theorem for inclusion-wise minimal set covers in -semi-ladder-free set systems. Although the number of minimal set covers of size at most may be as large as , we show that all such set covers can nevertheless be encoded by a family of at most tuples, and that this family can be enumerated in time . Combining this representation with a \textsc{Group Steiner Tree} subroutine, we obtain an algorithm for \textsc{Connected Set Cover}, which in turn yields an algorithm for \textsc{Connected Dominating Set} running in time and polynomial space. For the preprocessing result, we introduce grouped domination cores and dominator cores, and prove polynomial upper bounds on their sizes in -semi-ladder-free graphs. Using these structures, we obtain, for every fixed and , a polynomial-time -lossy compression for \textsc{Connected Dominating Set} to an equivalent reduced instance of size . The reduced instance is a \textsc{Connected Dominating Set} instance on a -semi-ladder-free graph.
Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: This is an archived version of the paper accepted at ISAAC 2026