2017/11/29 by Tung-Wei Kuo, Kuo, Tung-Wei
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1711.10680
openalex publication_date 2017/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the problem of minimum connected dominating set with routing cost constraint, we are given a graph G=(V,E), and the goal is to find the smallest connected dominating set D of G such that, for any two non-adjacent vertices u and v in G, the number of internal nodes on the shortest path between u and v in the subgraph of G induced by D ∪ \u,v\ is at most α times that in G. For general graphs, the only known previous approximability result is an O(log n)-approximation algorithm (n=|V|) for α= 1 by Ding et al. For any constant α> 1, we give an O(n^1-\frac1α(log n)^\frac1α)-approximation algorithm. When α≥ 5, we give an O(√(n)log n)-approximation algorithm. Finally, we prove that, when α=2, unless NP ⊆ DTIME(npolylog n), for any constant ε> 0, the problem admits no polynomial-time 2^log1-εn-approximation algorithm, improving upon the Ω(log n) bound by Du et al. (albeit under a stronger hardness assumption).