CS Paper Radar

The Minimum-Weight Mixed Dominating Set on Threshold Graphs

Emiliano Lancini, Oulin Yang

cs.DS cs.DM ·submitted 2026-08-11 15:24 UTC · v2

Abstract

We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of minimum total weight that dominates every vertex and edge of the graph. We first show that arbitrary weights can be reduced to non-negative weights without changing the asymptotic running time. By adapting a reduction to the minimum-weight edge cover given in Ferrarini, Kober, Lancini, and Yuditsky, we obtain an $\mathcal{O}(n^5)$-time algorithm for the minimum weight mixed dominating set problem on threshold graphs.

Comment
11 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

Parameterized algorithms for representing graphs as intersections of threshold graphs

cs.DS ·2026-10-12 ·L. Sunil Chandran, Suraj Kumar Sahoo
similarity 0.65
Abstract

A graph is called a threshold graph if there is an assignment of real valued weights to its vertices such that two vertices have an edge between them if and only if the sum of the weights of the two vertices is above a certain `threshold value'. We will denote the class of all threshold graphs as $TH$. For a graph $G=(V,E)$, if for some integer $t\geq 0$, there are $t$ many threshold graphs $\{G_i=(V,E_i)\}_{i\in [t]}$ such that we have $E=E_1\cap E_2\cap \cdots \cap E_t$, then we say that the collection of threshold graphs $\{G_i=(V,E_i)\}_{i\in [t]}$ forms a $TH$-representation of $G$ of size $t$. \emph{The intersection dimension of $G$ with respect to threshold graphs} (denoted as $dim_{TH}(G)$) is the smallest non-negative integer $t$ such that there is a $TH$-representation of $G$ of size $t$. It is known that for a graph $G$ and integer $t>0$, the problem of deciding whether $dim_{TH}(G)\leq t$ is NP-complete even for $t=3$. In this paper, we study this problem in the framework of parameterized algorithms. We consider the vertex cover number and the cluster vertex deletion number as our parameters. We give a FPT algorithm for determining an optimal $TH$-representation of a graph when parameterized by its vertex cover number. Our main result is an efficient parameterized approximation scheme for this problem when parameterized by the cluster vertex deletion number of $G$.

0.20

Near-Optimal Distributed Domination in Planar Graphs

cs.DS cs.DC ·2026-09-26 ·Wojciech Wawrzyniak
theoryhighly cited similarity 0.63
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 note on efficient k-limited broadcast domination in graphs

cs.DS math.CO ·2026-08-20 ·Bharadwaj, A. Senthil Thilak
theoryhot direction similarity 0.63
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

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

cs.CC ·2026-08-19 ·Chenghua Liu, Boning Meng
theory similarity 0.62
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.62
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

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

cs.DM math.CO ·2026-11-17 ·Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou
theory similarity 0.61
Abstract

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

0.18

Almost tight distributed approximation for domination in sparse graph classes

cs.DC cs.DMcs.DS ·2026-10-22 ·Timothé Picavet
similarity 0.61
Abstract · 27 pages, 4 figures

We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.

0.33