b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results

摘要

Let G = (V,E) be a connected graph with at least two vertices. For a fixed positive integer b ＞ 1, a set D is contained in V is called a b-disjunctive total dominating set of G if for every vertex v ∈ V, v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The minimum cardinality of a 6-disjunctive total dominating set of G is called the b-disjunctive total domination number of G, and is denoted by γ_b~(td)(G). The Minimum b-Disj Total Domination problem is to find a b-disjunctive total dominating set of cardinality γ_b~(td) (G). Given a positive integer k and a graph G, the b-Disj Total Dom Decision problem is to decide whether G has a b-disjunctive total dominating set of cardinality at most k. In this paper, we initiate the algorithmic study of the Minimum b-Disj Total Domination problem. We prove that the b-Disj Total Dom Decision problem is NP-complete even for bipartite graphs and chordal graphs, two important graph classes. On the positive side, we propose a In(Δ~2 + (b - 1)Δ) + 1-approximation algorithm for the Minimum b-Disj Total Domination problem. We prove that the Minimum b-Disj Total Domination problem cannot be approximated within 1/2(1-ε)In|V| for any ε ＞ 0 unless NP is contained in DTIME(|V|~(O(log log|V|))). Finally, we show that the Minimum b-Disj Total Domination problem is APX-complete for bipartite graphs with maximum degree b + 3.