TY - GEN
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, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
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 atleast 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 G[D], 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 remains NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the positive side, the problem is efficiently solvable for many graph classes including intervals graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graph. 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. (in Theor. Comput. Sci., 591 (2015 ) : 99 - 105 and Algorithmica, 82 (2020 ) : 2809 - 2840 ).
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 atleast 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 G[D], 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 remains NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the positive side, the problem is efficiently solvable for many graph classes including intervals graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graph. 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. (in Theor. Comput. Sci., 591 (2015 ) : 99 - 105 and Algorithmica, 82 (2020 ) : 2809 - 2840 ).
KW - AT-free graphs
KW - Approximation algorithm
KW - Domination
KW - Graph algorithms
KW - NP-completeness
KW - Paired domination
KW - Planar graphs
UR - http://www.scopus.com/inward/record.url?scp=85124667753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85124667753&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-95018-7_6
DO - 10.1007/978-3-030-95018-7_6
M3 - Conference contribution
AN - SCOPUS:85124667753
SN - 9783030950170
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 65
EP - 77
BT - Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Proceedings
A2 - Balachandran, Niranjan
A2 - Inkulu, R.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022
Y2 - 10 February 2022 through 12 February 2022
ER -