PaperlayerView exact revision on arXiv

Source-linked AI summary

Connected Dominating Set on Semi-Ladder-Free Graphs

Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana

arXiv:2609.39666v1cs.DS

TL;DR

The paper studies Connected Dominating Set on broader structurally restricted graph classes, while domination problems are W[2]-hard parameterized by solution size in general. It develops compact representations for minimal covers and core structures for preprocessing. Its stated algorithmic bound is for Connected Set Cover on d-semi-ladder-free systems, and its preprocessing extends lossy methods beyond previously considered graph classes.

  • Problem

    The paper studies Connected Dominating Set on broader structurally restricted graph classes, while domination problems are W[2]-hard parameterized by solution size in general.

    Source: §1 · p. 2

  • Method

    It groups inclusion-wise minimal covers into tuples and introduces grouped domination and dominator cores to aggregate redundant domination constraints.

    Source: §1 · p. 3

  • Results

    The representation family has size at most k^(kd+1) and enumeration time k^(kd+2)·O(nm); Conn-SC runs in k^(kd+2)·2^k·n^O(1) time, using polynomial space.

    Source: §1 · p. 3

  • Takeaways & Limitations

    This extends lossy preprocessing beyond the graph classes considered previously.

    Source: §1 · p. 4

    The bounds assume fixed d; with unbounded semi-ladder index, compact representations cannot have any FPT size bound.

    Source: §2 · p. 5, §3.1.3 · p. 10

Abstract

from arXiv · show

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^{\Omega(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.

1 Introduction

The introduction studies Connected Dominating Set on broader structurally restricted graph classes, using compact representations for connectivity-constrained covering and new core structures for approximate preprocessing.

1 Introduction

  • The paper targets Connected Dominating Set beyond previously studied structural graph classes, where the connected problem lacks polynomial kernels even on some sparse classes.Lossy kernelization provides a framework that trades approximation for polynomial-size compression.Source: §1 · p. 2
  • A bounded family of tuples compactly represents minimal set covers by encoding covers formed by choosing one set from each tuple subfamily.For d-semi-ladder-free systems, the representation has size at most k^(kd+1) and can be enumerated in k^(kd+2)·O(nm) time.Source: §1 · p. 3
  • Compact representations are necessary to avoid potentially large minimal-cover families, and the paper proves lower bounds tight up to polynomial factors in the exponent.For general set systems, it also establishes an unconditional impossibility result for FPT-sized compact representations.Source: §1 · p. 3
  • The compact-representation framework yields a polynomial-space Connected Set Cover algorithm, and consequently a fixed-parameter algorithm for Connected Dominating Set.The Connected Set Cover running time is k^(kd+2)·2^k·n^O(1).Source: §1 · p. 3
  • Grouped domination cores and dominator cores capture redundancy in domination constraints and have sizes at most kd and O(kd^2), respectively.Both cores are computable in polynomial time; grouped cores require each group to be dominated as a whole, while dominator-core classes are interchangeable for minimal dominating sets of size at most k.Source: §1 · pp. 3–4
  • For every fixed d and ε>0, Connected Dominating Set admits a polynomial-time (1+ε)-lossy compression of size k^O(d^2/ε) to instances on (d+2)-semi-ladder-free graphs.The introduction presents this as extending lossy preprocessing beyond graph classes considered previously.Source: §1 · p. 4

2 Preliminaries

The preliminaries define Connected Dominating Set and the semi-ladder-free restrictions used throughout, then introduce connectivity and approximate-compression tools.

2 Preliminaries

  • Connected Dominating Set asks for at most k vertices whose induced subgraph is connected and whose closed neighborhoods cover every graph vertex..Source: §2 · p. 4
  • A graph is d-semi-ladder-free when its closed-neighborhood set system satisfies the corresponding semi-ladder-free condition.The system uses vertices as its universe and one indexed closed neighborhood per vertex; repeated neighborhood subsets retain their vertex indices.Source: §2 · p. 4
  • The paper treats d as fixed, and defines the semi-ladder index as the smallest q for which the graph is (q+1)-semi-ladder-free.Source: §2 · p. 5
  • Group Steiner Tree seeks a minimum-size tree containing at least one vertex from each of ℓ disjoint groups, and is solvable in 2^ℓ·n^O(1) time using polynomial space.Source: §2 · p. 5
  • The semi-ladder-free class generalizes biclique-free graphs: the introduction to this relation identifies the 6d-semi-ladder-free class as a superclass of Kd,d-free graphs.The stated connection is established through a semi-induced version of semi-ladders.Source: §2 · p. 5
  • An approximate compression reduces an instance to a bounded-size instance and provides a solution-lifting algorithm with the specified approximation factor.A lossy compression maps a problem to itself or another problem; for minimization, the approximate parameter transformation compares the lifted solution with the original optimum.Source: §2 · p. 5

3 Connected Set Cover of d-semi-ladder-free set systems

The section develops a compact-representation approach to connected covering on d-semi-ladder-free set systems and applies it to Connected Dominating Set. It replaces direct enumeration of potentially numerous minimal covers with tuples that support connectivity-constrained algorithms.

3 Connected Set Cover of d-semi-ladder-free set systems

  • The section’s structural result yields a fixed-parameter algorithm for Conn-SC on d-semi-ladder-free set systems.Source: §3 · p. 6
  • The Conn-SC algorithm uses compact representations of minimal covers and a Group Steiner Tree subroutine to enforce connectivity.Source: §3 · p. 6

3.1.1 There can be XP-many minimal set covers

  • Even planar K2,2-free incidence graphs can have m^k inclusion-wise minimal set covers, making direct enumeration potentially XP-large.Source: §3.1.1 · p. 7

3.1.2 Compact Representation via Tuples

  • A compact representation groups minimal covers into tuples while requiring every choice of one set per position to remain a valid cover.Source: §3.1.2 · p. 8

3.1.3 Tightness and Impossibility Results

  • For d-semi-ladder-free systems, the representation is bounded by k^(Ω(kd)) in the lower-bound construction, while unbounded semi-ladder index precludes any FPT-size bound in general.Source: §3.1.3 · p. 10

3.2 Applications of compactly representing all minimal set covers

  • Connected Dominating Set on d-semi-ladder-free graphs admits an algorithm running in k^(kd+2)·2^k·n^O(1) time and polynomial space.Source: §3.2 · p. 11

4 Cores for Dominators and Domination Requirements

The section develops parameter-k cores that compress domination requirements while preserving the behavior of small minimal dominating sets. A grouping operation supports recursive core construction and preserves semi-ladder-freeness.

4 Cores for Dominators and Domination Requirements

  • A k-dominator core partitions vertices into disjoint classes so each minimal dominating set of size at most k uses at most one vertex per class, with members interchangeable for domination.The core size is the number of classes.Source: §4 · p. 11
  • The target bounds are kd for grouped domination cores and O(kd^2) for dominator cores in d-semi-ladder-free graphs.The cores are computed in polynomial time.Source: §4 · pp. 11–12
  • A k-grouped domination core consists of disjoint batches that small minimal dominating sets collectively dominate, and any set dominating every batch dominates the graph.The section also frames domination of a family as having one vertex dominate each entire batch.Source: §4 · p. 11
  • Group replaces a subset of the universe with one representative while updating represented sets, and preserves d-semi-ladder-freeness.The operation also preserves domination and grouping properties, with dominating sets corresponding naturally to those in the original graph.Source: §4 · pp. 11–12
  • FindCore recursively compresses the universe while preserving domination structure to construct both types of cores.Its stated output is a k-dominator core and a k-grouped domination core.Source: §4 · p. 12

5 Approximate compression for Conn-DS on d-semi-ladder-free graphs

The compression constructs a smaller connected dominating set instance by selecting and connecting representative vertices, then bounds its size and approximation guarantee. The reduced graph remains (d + 2)-semi-ladder-free, and solutions can be lifted without increasing their size.

5 Approximate compression for Conn-DS on d-semi-ladder-free graphs

  • The construction adds heavy vertices representing subsets and retains original vertices as non-heavy vertices in an augmented graph.Each heavy vertex is adjacent to original vertices adjacent to every member of its represented subset.Source: §5 · p. 12
  • For subsets of the dominator core of size at most 2t, Group Steiner Tree finds trees whose vertices are marked; if the marked set does not dominate G, the algorithm returns a trivial NO-instance.The marked set is then connected by adding at most 2|M| vertices, and the returned graph is induced by the marked vertices, connectors, heavy vertices, and their neighborhood.Source: §5 · p. 13
  • The resulting induced graph G′ is (d + 2)-semi-ladder-free.This follows from the augmentation lemma and closure of semi-ladder index under induced subgraphs.Source: §5 · p. 13
  • Any connected dominating set of G′ can be lifted in polynomial time to one of G of no greater size.The compression uses cores of size O(kd^2) and kd, respectively.Source: §5 · pp. 12–13
  • The compressed instance I′ has polynomial size and OPT(I′, k) ≤ (1 + ϵ)OPT(I, k).This establishes the size and approximation guarantee used for the lossy compression.Source: §5 · p. 13

A.1 Basics of Parameterized Complexity

This appendix section introduces basic parameterized-complexity terminology, describing fixed-parameter tractability and the form of instances and solutions for a parameterized problem.

A.1 Basics of Parameterized Complexity

  • Fixed-parameter tractability means solving an instance (I, k) in time f(k) · |I|^O(1) for some computable function f.Dominating Set parameterized by solution size is given as an example.Source: §A.1 · p. 15
  • For a parameterized optimization problem Π, the section begins its definition by specifying Π as a computable function.Source: §A.1 · p. 15
  • A parameterized problem instance is a pair (I, k), and a solution is a string s with |s| ≤ |I| + k.The solution's value is denoted Π(I, k, s).Source: §A.1 · p. 15

B Missing proofs and details from Section 2

The proof shows that semi-induced d-semi-ladder-freeness rules out a 3d-semi-ladder. A greedy selection process extracts a forbidden d-semi-ladder from any supposed 3d example.

B Missing proofs and details from Section 2

C Missing proofs and details from Section 3

This section provides proofs and details for the compact representation of minimal set covers, its use in Connected Set Cover, and constructions showing limits on representation size. It also derives a polynomial-space algorithm for Connected Dominating Set on d-semi-ladder-free graphs from Connected Set Cover and a closed-neighborhood reduction.

Theorem 13

  • For every k,m, a set system has exactly mk inclusion-wise minimal set covers, while its incidence graph is planar and K2,2-free.Each cover consists of the set B and exactly one choice from each of k blocks of m sets.Source: C Missing proofs and details from… · pp. 16–17

Theorem 1

  • For d-semi-ladder-free systems, all minimal set covers of size at most k have a compact representation of at most k^(kd+1) tuples, enumerable in k^(kd+2)·O(nm) time.Each tuple has arity at most k.Source: C Missing proofs and details from… · pp. 18, 20

Lemma 22

  • Solve returns at most ℓ^μ tuples in ℓ^(μ+1)·O(nm) time; each tuple’s pairwise-disjoint families ensure every choice of one set per family covers the universe.The measure μ decreases across recursive branches, yielding the stated bounds.Source: C Missing proofs and details from… · pp. 18, 20

Representation lower bounds

  • When c=d−2, the set system is d-semi-ladder-free, and any compact representation of all minimal set covers of size at most k has size at least (k!)^(d−3).For any function f and constant q, there exist an integer k and set system (U,F) whose compact representation of all minimal set covers of size at most k is strictly greater than f(k)·(|U|+|F|)^q.Source: C Missing proofs and details from… · p. 21

Theorem 2

  • Connected Set Cover on d-semi-ladder-free systems is solvable in k^(kd+2)·2^k·n^O(1) time and polynomial space.The proof applies Group Steiner Tree to the groups in each tuple returned by the compact-representation algorithm.Source: C Missing proofs and details from… · p. 22

C Missing proofs and details from Section 3

  • For a YES Connected Set Cover instance, a minimal solution is encapsulated by a tuple, and Group Steiner Tree on that tuple returns a solution of size at most k.Any solution returned for a tuple also satisfies the coverage and connectivity requirements of Connected Set Cover.Source: C Missing proofs and details from… · p. 22
  • Connected Dominating Set on d-semi-ladder-free graphs is solvable in k^(kd+2)·2^k·n^O(1) time and polynomial space.Tuples are generated one at a time, requiring k·n^O(1) space rather than storing the full tuple family.Source: C Missing proofs and details from… · p. 22
  • A Connected Dominating Set instance becomes Connected Set Cover by using graph vertices as elements and closed neighborhoods as sets, with set edges mirroring graph edges.The two instances have solutions of size at most k exactly when the other does.Source: C Missing proofs and details from… · p. 22

C.1 Details of Remark 16

A single tuple compactly represents every inclusion-wise minimal set cover of size at most k + 1 in the constructed instance. Its disjoint component families cover the universe and capture every such cover.

C.1 Details of Remark 16

  • One tuple represents all inclusion-wise minimal set covers of size at most k + 1 for the constructed instance.The tuple is T⋆ = (F0, F1, . . . , Fk), with F0 = {B} and Fi containing the sets Si,j for each j.Source: §C.1 · p. 22
  • Every selection from the tuple’s component families covers the universe because B covers t and all bi,j, while one selected set per i covers ui.The families are pairwise disjoint: F0 contains B, and each Fi contains only sets Si,j with fixed first index i.Source: §C.1 · p. 23
  • Every minimal set cover of size at most k + 1 has the form {B} ∪ {S1,j1, . . . , Sk,jk}, so the tuple captures it.Each such cover has size k + 1 and can be ordered with B first and one set from each Fi.Source: §C.1 · p. 23

D Missing proofs and details from Section 4

The section proves polynomial-size grouped domination and dominator cores for d-semi-ladder-free graphs. Its inductive construction groups batches using a red-blue domination invariant, then applies the result to closed neighborhoods in the original graph.

D Missing proofs and details from Section 4

  • A polynomial-time algorithm computes a grouped domination core of size at most kd and a dominator core of size at most O(kd^2) in a d-semi-ladder-free graph.The same bounds are established for the base case when |U| ≤ kd.Source: D Missing proofs and details from… · p. 23
  • Red-blue domination translates whether a vertex set dominates G into whether its corresponding red vertices dominate an auxiliary bipartite instance.The proof maintains an invariant equating domination in G with red-blue domination for sets of size at most k.Source: D Missing proofs and details from… · p. 24
  • When |U| exceeds kd, the induction groups a set S from the intersection closure into one batch, chosen with |S| > kℓ(S).The counting argument ensures every dominating set of size at most k contains a vertex dominating the entire grouped batch.Source: D Missing proofs and details from… · pp. 24–25
  • The Group operation preserves the dominator-core properties by merging image sets and preserving domination and replacement behavior for minimal dominating sets.The proof also verifies that grouped batches retain collective domination and that domination of the new batches preserves domination of G.Source: D Missing proofs and details from… · p. 25
  • The recursive construction retains the red-blue invariant and reduces |U|, so induction yields the same core-size bounds for the original instance.For the original graph, the initialization uses V(G), closed neighborhoods, and singleton images under f and g.Source: D Missing proofs and details from… · p. 26

D.1 Pseudo-code of the Group operation

The Group operation forms a reduced universe by replacing the selected subset S with a new representative. It updates the family through a map that depends on whether each set contains S.

D.1 Pseudo-code of the Group operation

  • Group takes a set family F over U, functions f and g, and a selected subset S as input.Its required inputs include f : F → 2^V(G) and g : U → 2^V(G).Source: §D.1 · p. 27
  • The operation creates a new representative vS and replaces S in the universe with that representative.The resulting universe is U′ = (U \ S) ∪ {vS}.Source: §D.1 · p. 27
  • Each set A is mapped to (A \ S) ∪ {vS} when S ⊆ A, and otherwise to A \ S.The procedure returns the updated tuple (U′, F′, f′, g′).Source: §D.1 · p. 27

E Missing proofs and details of Section 5

For every fixed d and ε > 0, Connected Dominating Set on d-semi-ladder-free graphs admits a polynomial-time (1 + ε)-lossy compression of size k^O(d^2/ε) to a (d + 2)-semi-ladder-free instance. The proof bounds the reduced instance, constructs a near-optimal solution, and lifts solutions without increasing their size.

Lemma 31

  • The constructed graph has semi-ladder index at most d + 2 because deleting heavy vertices from an intersection-closure chain yields a chain in the original graph shorter by at most two.The resulting chain has length at least l − 2, so l ≤ d + 2.Source: E Missing proofs and details of… · pp. 27–28

Theorem 4

  • For fixed d and ε > 0, the compression has size k^O(d^2/ε) and outputs a Connected Dominating Set instance on a (d + 2)-semi-ladder-free graph.The reduced optimum is at most (1 + ε) times the original optimum.Source: E Missing proofs and details of… · pp. 28–29

Solution lifting

  • A polynomial-time lifting procedure replaces heavy vertices with batch vertices, preserving connectivity and domination while keeping the solution size no larger.The preservation property of the k-grouped domination core ensures the resulting original-graph solution dominates G.Source: E Missing proofs and details of… · pp. 28–29

Lemma 35

  • The reduced instance has polynomial size because the grouped domination core and dominator core bound the vertices and marked trees used in its construction.The proof bounds the core by |G| ≤ kd and the dominator core by O(kd^2), with t = Θ(1/ε).Source: E Missing proofs and details of… · p. 29

Approximation guarantee

  • The marking construction and added connectors yield a solution of size at most (1 + ε)OPT(I, k), using t ≥ 8/ε and a brute-force small-solution case.For OPT(I, k) > 8/ε, the proof bounds the marking and connector overhead by the ε allowance.Source: E Missing proofs and details of… · p. 29
Loading 2609.39666v1…