Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13431503 | Theoretical Computer Science | 2020 | 30 Pages |
Abstract
A set D of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to a vertex in D and the subgraph induced by D contains a perfect matching (not necessarily as an induced subgraph). A paired-dominating set of G is minimal if no proper subset of it is a paired-dominating set of G. The upper paired-domination number of G, denoted by Îpr(G), is the maximum cardinality of a minimal paired-dominating set of G. In Upper-PDS, it is required to compute a minimal paired-dominating set with cardinality Îpr(G) for a given graph G. In this paper, we show that Upper-PDS cannot be approximated within a factor of n1âε for any ε>0, unless P=NP and Upper-PDS is APX-complete for bipartite graphs of maximum degree 4. On the positive side, we show that Upper-PDS can be approximated within O(Î)-factor for graphs with maximum degree Î. We also show that Upper-PDS is solvable in polynomial time for threshold graphs, chain graphs, and proper interval graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, D. Pradhan,