## 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 n^{1−ε} 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.

Original language | English |
---|---|

Pages (from-to) | 98-114 |

Number of pages | 17 |

Journal | Theoretical Computer Science |

Volume | 804 |

DOIs | |

Publication status | Published - 12 Jan 2020 |

## Keywords

- APX-complete
- Domination
- NP-complete
- Paired-domination
- Polynomial time algorithm
- Upper paired-domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science