Complexity of distance paired-domination problem in graphs
Journal
Theoretical Computer Science
Journal Volume
459
Pages
89-99
Date Issued
2012
Author(s)
Abstract
Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D ⊆ V is a distance k-dominating set of G if for every u ∈ V, there exists a vertex v ∈ D such that dG(u, v) ≤ k, where dG(u, v) is the distance between u and v in G. A set D ⊆ V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph G[D] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the Min Distance k-Paired-Dom Set problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of Min Distance k-Paired-Dom Set is NP-complete for undirected path graphs. This strengthens the complexity of decision version of Min Distance k-Paired-Dom Set problem in chordal graphs. We show that for a given graph G, unless NP ⊆ DTIME (nO(log log n)), Min Distance k-Paired-Dom Set problem cannot be approximated within a factor of (1 - ε) ln n for any ε > 0, where n is the number of vertices in G. We also show that Min Distance k-Paired- Dom Set problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, Min Distance k-Paired-Dom Set problem can be approximated with an approximation factor of 1+ln 2+k · ln(Δ(G)), where Δ(G) denotes the maximum degree of G. © 2012 Elsevier B.V. All rights reserved.
SDGs
Type
journal article