CS Paper Radar

Complexity, Bounds, and Exact Algorithms for Rainbow $k$-Domination in Regular Graphs

Piotr Lange

cs.DM cs.CC ·submitted 2026-10-01 10:22 UTC · v1

Abstract

A rainbow $k$-dominating function assigns the empty set or exactly one of the colors $\{1\},\{2\},\ldots,\{k\}$ to each vertex of a simple graph in such a way that every vertex receiving $\emptyset$ sees all $k$ colors in its neighborhood. This model has several facility-location interpretations where colored vertices represent sites hosting different types of services, and uncolored vertices represent the beneficiaries of those services who must have access to all of them. In this paper we study this domination variant in regular graphs. First, we develop lower and upper bounds for this class of graphs, and explore their structural consequences. Then, we use those results to prove NP-completeness of a decision formulation of this problem. Additionally, we derive exact formulas for the rainbow $k$-domination number of cycles, Möbius ladders and prisms. Lastly, we develop a dynamic-programming algorithm for generalized Petersen graphs of the form $P(6t, t)$ and state two conjectures based on the output of its implementation and related integer linear programming computations.

Closest papers

Nearest neighbours by meaning across the whole index.

A Graph Theoretic Approach to Spatial Modeling of Post Disaster Shelter Camps Using Rainbow and Roman Domination Parameters

cs.DM ·2026-09-30 ·Didem Gözüpek, Piotr Lange, Joanna Raczek
similarity 0.73
Abstract

Effective spatial organization of post-disaster shelter camps is essential for ensuring access to basic services while making efficient use of limited space and resources. In this paper, we propose a graph-theoretic framework for shelter-camp facility placement based on rainbow $k$-domination and Roman domination. Rainbow $k$-domination models the simultaneous accessibility of distinct facility types, such as sanitation units, kitchens, water points, and schools, whereas Roman domination is used to represent services with different capacity levels, illustrated through Wi-Fi deployment. We present an $O(nk)$-time algorithm for finding a minimum rainbow $k$-dominating set of a tree with $n$ vertices, which is linear in $n$ for fixed $k$, and computational experiments confirm its scalability on large instances. For general graphs, we establish new lower and upper bounds on the rainbow $k$-domination number. We further investigate its relationship with Roman domination, derive structural properties of graphs attaining the extremal equality between the two parameters, and prove that recognizing such graphs is NP-hard. These results provide a theoretical foundation for domination-based approaches to facility placement in post-disaster shelter planning.

0.49

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

Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness

cs.DM math.CO ·2026-11-02 ·Kamal Santra
theory similarity 0.70
Abstract

A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound $ω(G)\leq\pcf(G)\leqω(G)+1$ and give an $O(n^2)$ construction from a partition tree. Every assignment of lists of at least $ω(G)+1$ colors also admits a PCF coloring that respects the lists. Deciding whether $ω(G)$ colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size $ω(G)+1$ always suffice, improving the previous ordinary-coloring bound of $ω(G)+2$. We use matchings to characterize when $ω(G)$ colors suffice and give an endpoint algorithm taking $2^{O(ω(G)^2)}n^{O(1)}$ time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking $O(n^{33})$ time. For bipartite permutation graphs, a smaller dynamic program gives an exact $O(n^{17})$ algorithm. Finally, if a bipartite graph is convex over an ordered shore $X$, we prove the sharp bound $\pcf(G)\leq\lceil\log_2(|X|+1)\rceil+3$ and construct a coloring in linear time from the order.

0.36

Complexity and algorithms for proper conflict-free coloring in graphs

cs.DM math.CO ·2026-08-11 ·Dinabandhu Pradhan, Vaishali Sharma
similarity 0.70
Abstract

A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $χ_{pcf}(G)\leq ω(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.

0.41

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.69
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16

Graph Coloring with Color Preferences

cs.GT math.CO ·2026-09-01 ·Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda
theory similarity 0.68
Abstract

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $χ_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $χ_\mathrm{stable}(G)$. This shows that $χ_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.

0.16

Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs

cs.DM math.CO ·2026-11-04 ·Gautam K. Das, Kamal Santra
theory similarity 0.68
Abstract

A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size $k\ge4$. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in $O(n+m)$ time, where $n$ and $m$ count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most $s$, we give an exact algorithm in $n^{2^{O(s+1)}}$ time, with no bound on the clique number.

0.12

Combinatorial optimization with bounded subdeterminants

cs.DS cs.DMmath.COmath.OC ·2026-11-09 ·Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon +3 more
similarity 0.67
Abstract · 25 pages

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

0.20