CS Paper Radar

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

Manjusha M S, Renjith P

cs.DM ·submitted 2026-08-11 08:00 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.75
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

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.71
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.68
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

A Linear Kernel for Planar Semitotal Domination

cs.DS ·2026-10-27 ·Paloma T. de Lima, Lukas Retschmeier
similarity 0.67
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.

0.15

A note on efficient k-limited broadcast domination in graphs

cs.DS math.CO ·2026-08-20 ·Bharadwaj, A. Senthil Thilak
theoryhot direction similarity 0.67
Abstract · 10 pages, 2 figures

An efficient $k$-limited dominating broadcast, or $k$-ELDB, is a $k$-limited broadcast in which every vertex is dominated exactly once. This notion brings together efficient domination and limited broadcast domination in a common framework. For a graph $G$, we write $mcr(G)$ for the smallest integer $k$ for which $G$ admits a $k$-ELDB. For an admissible value $k\ge mcr(G)$, we denote by $γ_{ebk}(G)$ the minimum cost of a $k$-ELDB on $G$, and is called the $k$-efficient broadcast domination number of $G$. In this paper, we study these parameters from an algorithmic perspective with complexity analysis. We develop a dynamic programming algorithm for trees which, for fixed $k$, computes $γ_{ebk}(T)$ and thereby obtains a polynomial-time procedure for determining $mcr(T) $. In contrast, we prove that, for every fixed integer $k\ge 1$, deciding whether a graph admits a $k$-ELDB is NP-complete for arbitrary graphs. These results place efficient limited broadcast domination in a natural complexity framework, with trees forming a tractable class and arbitrary graphs remaining computationally hard.

0.27

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

cs.DM math.CO ·2026-11-16 ·Florent Foucaud, Yan Gerard, Christian Laforest, Le Vu Pham
published similarity 0.66
Abstract · 23 pages, 5 figures. Appears in the Proceedings of the 52nd International Conference on Current Trends in Theory and Practice of Computer Sc…

A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. Hedetniemi and Rall asked for the largest constant $c$ with $\mathrm{ud}^*(T) \geq c \cdot n$ for every tree $T$ of order $n$. We answer their question: the constant is $4/5$, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study $\mathrm{ud}^*$ under each of the two requirements separately, giving the Full-Cover variant $\mathrm{ud}^*_0$ and the Non-Overlapping variant $\mathrm{ud}^*_+$. The two behave very differently: on arbitrarily large graphs $\mathrm{ud}^*_0$ may remain bounded by a constant, whereas $\mathrm{ud}^*_+$ always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds $\lceil \sqrt[c]{n} \rceil$ and $4\sqrt{n}$, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

0.55

Lower Bounds for Domination-Type Problems Parameterized by Rank-Width

cs.CC ·2026-08-19 ·Chenghua Liu, Boning Meng
theory similarity 0.66
Abstract

For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((σ,ρ)\)-problems and of Bergougnoux and Kanté (\emph{SIAM J. Discrete Math.}, 2021) for Connected Dominating Set run in \(2^{O(w^2)}n^{O(1)}\) time. Bergougnoux, Korhonen, and Nederlof (STACS 2023) proved a matching lower bound under the Exponential Time Hypothesis (ETH) for \emph{Weighted} Dominating Set, but left the unweighted problem open. We prove that, unless ETH fails, Dominating Set admits no \(2^{o(w^2)}n^{O(1)}\)-time algorithm, even on split graphs and, separately, on bipartite graphs of diameter at most four, and even with a rank-decomposition or witnessing vertex order supplied. The proof replaces the earlier weights by a two-guard gadget and uses a low-rank equality gadget to carry \(k^2\) assignment bits through cuts of rank \(O(k)\). The construction also gives the same lower bound for Independent, Connected, and Total Dominating Set on restricted graph classes and applies to a broad family of \((σ,ρ)\)-set problems. This family includes cases in which \(σ\) is neither finite nor cofinite and contains the entire nontrivial cofinite--cofinite minimization regime. Every solution within the target budget has target size and corresponds bijectively to a satisfying assignment. Under the counting Exponential Time Hypothesis (\(\#\mathrm{ETH}\)), the same bounds therefore hold for counting solutions of size at most or exactly the target. Together with the known algorithms, our results show that the quadratic dependence on the rank-width \(w\) is optimal up to constant factors in the exponent for the classical problems above and throughout the covered finite/cofinite regime.

0.18

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.66
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