TY - JOUR

T1 - Complexity of paired domination in AT-free and planar graphs

AU - Tripathi, Vikash

AU - Kloks, Ton

AU - Pandey, Arti

AU - Paul, Kaustav

AU - Wang, Hung Lung

N1 - Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/9/21

Y1 - 2022/9/21

N2 - For a graph G=(V,E), a subset D of vertex set V, is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set), if the subgraph induced by D in G has a perfect matching. The MIN-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the MIN-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G=(V,E), it is NP-hard to decide whether γ(G)=γpr(G). In this paper we settle this conjecture affirmatively.

AB - For a graph G=(V,E), a subset D of vertex set V, is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set), if the subgraph induced by D in G has a perfect matching. The MIN-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the MIN-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G=(V,E), it is NP-hard to decide whether γ(G)=γpr(G). In this paper we settle this conjecture affirmatively.

KW - Approximation algorithm

KW - AT-free graphs

KW - Domination

KW - Graph algorithms

KW - NP-completeness

KW - Paired domination

KW - Planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85134806639&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134806639&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.07.010

DO - 10.1016/j.tcs.2022.07.010

M3 - Article

AN - SCOPUS:85134806639

VL - 930

SP - 53

EP - 62

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -