Complexity of paired domination in at-free and planar graphs

DOI10.1007/978-3-030-95018-7_6MaRDI QIDQ6102264zbMATH OpenOpenAlexFDO

Authors Vikash Tripathi, Ton Kloks, Arti Pandey, Kaustav K. Paul, Hung-Lung Wang

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.05486

zbMATH Keywords

approximation algorithmat-free graphsdominationgraph algorithmsNP-completenesspaired dominationplanar graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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$).

Cites work

• A linear-time algorithm for paired-domination on circular-arc graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Approximating the bandwidth for asteroidal triple-free graphs
• Asteroidal Triple-Free Graphs
• Domination and total domination on asteroidal triple-free graphs
• Face covers and the genus problem for apex graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Labelling algorithms for paired-domination problems in block and interval graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Paired domination in graphs: a survey and recent results
• Paired-domination in graphs
• Paired-domination problem on distance-hereditary graphs
• Topics in Domination in Graphs

Cited in

(4)

• Complexity of paired domination in AT-free and planar graphs
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Linear-time algorithm for paired-domination on distance-hereditary graphs
• Grouped domination parameterized by vertex cover, twin cover, and beyond

This page was built for publication: Complexity of paired domination in at-free and planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102264)