Complexity of Paired Domination in AT-free and Planar Graphs

Vikash Tripathi, Ton Kloks, Arti Pandey*, Kaustav Paul, Hung Lung Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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

Original languageEnglish
Title of host publicationAlgorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Proceedings
EditorsNiranjan Balachandran, R. Inkulu
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages13
ISBN (Print)9783030950170
Publication statusPublished - 2022
Event8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022 - Puducherry, India
Duration: 2022 Feb 102022 Feb 12

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13179 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022


  • AT-free graphs
  • Approximation algorithm
  • Domination
  • Graph algorithms
  • NP-completeness
  • Paired domination
  • Planar graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Complexity of Paired Domination in AT-free and Planar Graphs'. Together they form a unique fingerprint.

Cite this