Algorithmic aspects of upper paired-domination in graphs

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-dominat...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-01, Vol.804, p.98-114
Main Authors: Henning, Michael A., Pradhan, D.
Format: Article
Language:English
Subjects:
APX-complete
Domination
NP-complete
Paired-domination
Polynomial time algorithm
Upper paired-domination
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.10.045