Complexity and Approximation Algorithm of 3-Component Domination in Graphs
摘要
Let s be an integer and \(G=(V, E)\) be a graph. A subset \(D \subseteq V\) is called an s-component dominating set of \(G=(V, E)\) if every vertex \(v \in V \setminus D\) is adjacent to a vertex in D and each component of G[D] has at least s vertices. The s-component domination number of \( G=(V, E) \) , denoted as \( \gamma _s(G)\) , is the minimum cardinality among all s-component dominating sets of G. Note that an s-component dominating set is just a dominating set for \(s=1\) and a total dominating set for \(s=2\) . Given a graph G and a positive integer k, the Decide 3-comp Dom is the problem to decide whether G admits a 3-component dominating set of cardinality at most k, and Min 3-comp Dom is the problem of computing \(\gamma _3(G)\) . In this paper, we first show the complexity difference between domination and 3-component domination. We, then, show that Decide 3-comp Dom is NP-complete for bipartite graphs as well as for chordal graphs. We also show that Min 3-comp Dom is \(\frac{3}{2}(1+\ln {\varDelta })\) -approximable for general graphs, where \(\varDelta \) is the maximum degree of G. Next, we show that Min 3-comp Dom cannot be approximated within \((1-\epsilon )\ln {|V|}\) for any \(\epsilon >0\) unless \(\textsf {P}=\textsf {NP}\) even when \(G=(V, E)\) is bipartite and even when \(G=(V, E)\) is chordal. We prove that Min 3-comp Dom for bounded degree graphs admits a constant approximation algorithm. Finally, we show that Min 3-comp Dom is APX-complete for bipartite graphs with maximum degree 4.