2013/01/07 by Klaus-Tycho Foerster · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Dominating set #Combinatorics #Approximation algorithm #Mathematics #Graph #Domination analysis #Discrete mathematics #Connected dominating set #Set (abstract data type) #Computer science #Vertex (graph theory)
paper · doi:10.1137/1.9781611973037.4
openalex publication_date 2013/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we study the NP-complete problem of finding small k-dominating sets in general graphs, which allow k − 1 nodes to fail and still dominate the graph. The classic minimum dominating set problem is a special case with k = 1. We show that the approach of having at least k dominating nodes in the neighborhood of every node is not optimal. For each α > 1 it can give solutions k/α times larger than a minimum k-dominating set. We also study lower bounds on possible approximation ratios. We show that it is NP-hard to approximate the minimum k-dominating set problem with a factor better than (0.2267/k) ln(n/k). Furthermore, a result for special finite sums allows us to use a greedy approach for k-domination with an approximation ratio of ln(Δ + k) + 1 < ln(Δ) + 1.7, with Δ being the maximum node-degree. We also achieve an approximation ratio of ln(n) + 1.7 for h-step k-domination, where nodes do not need to be direct neighbors of dominating nodes, but can be h steps away.