Algorithm and complexity of the two disjoint connected dominating sets problem on trees

摘要

In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G=(V,E) and required to find a new edge set E′ with minimum cardinality such that the resulting new graph after the adding of E′ has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP-hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 32 asymptotically.