CS Paper Radar

A Linear Kernel for Planar Semitotal Domination

Paloma T. de Lima, Lukas Retschmeier

cs.DS ·submitted 2026-10-27 14:16 UTC · v1

Abstract

A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within distance at most two. The Semitotal Domination problem asks whether $G$ admits such a set of size at most $k$. We study this problem parameterized by the solution size. We provide a linear kernel of size $358k$ on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is $W[2]$-hard on split graphs, on bipartite graphs and on $t$-claw-free graphs, it is $W[1]$-hard on circle graphs.

Closest papers

Nearest neighbours by meaning across the whole index.

Connected Dominating Set on Semi-Ladder-Free Graphs

cs.DS ·2026-09-30 ·Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana
publishedtheory similarity 0.73
Abstract · This is an archived version of the paper accepted at ISAAC 2026

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.

0.22

Near-Optimal Distributed Domination in Planar Graphs

cs.DS cs.DC ·2026-09-26 ·Wojciech Wawrzyniak
theoryhighly cited similarity 0.71
Abstract · 19 pages, 7 figures

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

0.36

A Fine-Grained Complexity of Co-Secure Domination for Some Subclasses of Chordal Graphs

cs.DM ·2026-08-11 ·Manjusha M S, Renjith P
similarity 0.67
Abstract

For a connected graph $G = (V, E)$, a set $D \subseteq V$ is a co-secure dominating set if $D$ is a dominating set of $G$ and for each vertex $u \in D$ there exists a vertex $v \in V \setminus D$ such that $uv \in E$ and $(D \setminus \{u\}) \cup \{v\}$ is a dominating set of $G$. In this article, we present bounds on the co-secure domination number (size of minimum co-secure dominating set) in some restricted 2-trees, a popular subclass of chordal graphs. We also show an interesting dichotomy that the co-secure dominating set problem is NP-complete on $K_{1,r}$-free split graphs, $r\ge 4$, whereas it is linear-time solvable on $K_{1,3}$-free split graphs.

0.04

Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs

cs.DS ·2026-09-01 ·Ajinkya Gaikwad
similarity 0.67
Abstract

The \emph{$s$-Club Cluster Edge Deletion} problem asks whether, given a graph $G$ and an integer $k$, one can delete at most $k$ edges so that every remaining connected component has diameter at most~$s$. This generalizes the classical \emph{Cluster Edge Deletion} problem by permitting components of bounded diameter instead of requiring cliques. On general graphs, $2$-Club Cluster Edge Deletion is known to be fixed-parameter tractable when parameterized by $k$, but it remains open whether it admits a polynomial kernel, as posed in~\cite{ABUKHZAM2023113864}. Motivated by this question, we study the problem on interval graphs and obtain a polynomial vertex kernel of size $\mathcal{O}(k^{5})$. As a complementary result, we also show that the \emph{$s$-Club Cluster Edge Deletion} problem is polynomial time solvable on unit interval graphs. We also show that $2$-Club Cluster Edge Deletion is NP-hard even on split graphs.

0.17

Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

cs.DS ·2026-11-10 ·Yuma Tamura, Daichi Wakayama, Akira Suzuki, Xiao Zhou
published similarity 0.67
Abstract · Accepted for publication in IPEC2026

The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. $(σ, ρ)$-Dominating Set problem. Given a graph $G$ and a positive integer $\ell$, Minimum Membership Dominating Set asks whether there is a dominating set $D$ such that every vertex in $G$ is dominated by at most $\ell$ vertices in $D$. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus $\ell$ is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. $(σ, ρ)$-Dominating Set problem parameterized by asteroidal number plus $μ$, where $σ$ and $ρ$ are finite sets of non-negative integers and $μ$ is the maximum value in $σ\cup ρ$. Note that asteroidal number generalizes leafage to arbitrary graphs. Combining this algorithm with our structural bound that every graph $G$ admits a dominating set such that no vertex is dominated by more than $7\mathsf{an}(G)-6$ vertices, where $\mathsf{an}(G)$ denotes the asteroidal number of $G$, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.

0.32

A Counterexample to Teschner's Bondage-Number Conjecture

cs.DM math.CO ·2026-09-01 ·Yousof Yavari
theory similarity 0.66
Abstract · 9 pages, no figures; complete Python 3 verifier included in the appendix

For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $γ(G)$. Teschner conjectured that $b(G)\le \tfrac32Δ(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ γ(G)=6 \qquad\text{and}\qquad b(G)=5. \] The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its $\binom{27}{4}=17{,}550$ four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.

0.21

Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion

cs.DS cs.CC ·2026-10-13 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
similarity 0.65
Abstract · Full version of an IPEC 2026 contribution. Abstract has been shortened for arXiv

For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

0.26

Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation

cs.DM ·2026-10-07 ·Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
similarity 0.65
Abstract · Submitted to CALDAM 2027

A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.

0.09