Efficient connected domination algorithms for special graph classes
Connected Dominating Set on Semi-Ladder-Free Graphs
Data Structures and Algorithms
Summary
This paper looks at a problem called Connected Dominating Set, where you want to pick a small group of connected points in a network so that every point is either in that group or next to someone in it. The authors study this problem for networks that avoid a complicated pattern called a "semi-ladder," which is more general than what was studied before. They found a way to summarize all minimal solutions compactly and use this to design an algorithm that works well when the solution size and pattern complexity are small. They also show how to shrink these problems to smaller ones without losing much accuracy.
What this means in practice
- •For network operators: Optimize placement of control or monitoring nodes in special networks where avoiding complex substructures helps efficient solutions.
- •For graph algorithm developers: Incorporate compact representations of minimal set covers into tools for handling connectivity-constrained domination problems more efficiently.
A theory result. No direct application yet.
Authors
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana
Abstract
We study \textsc{Connected Dominating Set} on graphs whose closed-neighborhood set systems are $d$-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 $d$-semi-ladder-free set systems. Although the number of minimal set covers of size at most $k$ may be as large as $n^{Ω(k)}$, we show that all such set covers can nevertheless be encoded by a family of at most $k^{kd+1}$ tuples, and that this family can be enumerated in time $\Oh(k^{kd+2}\cdot nm)$. 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 $k^{kd+2}\cdot 2^k \cdot n^{\Oh(1)}$ and polynomial space. For the preprocessing result, we introduce grouped domination cores and dominator cores, and prove polynomial upper bounds on their sizes in $d$-semi-ladder-free graphs. Using these structures, we obtain, for every fixed $d$ and $\varepsilon>0$, a polynomial-time $(1+\varepsilon)$-lossy compression for \textsc{Connected Dominating Set} to an equivalent reduced instance of size $k^{\Oh(d^2/\varepsilon)}$. The reduced instance is a \textsc{Connected Dominating Set} instance on a $(d+2)$-semi-ladder-free graph.