Complexity of Paired Domination Problems on Circle and k-Polygon Graphs

2024/11/29 by Ta-Yu Mu, Mu, Ta-Yu, Ching‐Chi Lin +1
Computer Science · #Optimization and Search Problems #Computational Geometry and Mesh Generation #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2411.19473

Abstract

A set D ⊆ V is a dominating set of a graph G if every vertex in V - D is adjacent to at least one vertex in D. A dominating set D is a paired-dominating set if the subgraph of G induced by D contains a perfect matching. In this paper, we prove that determining the minimum paired-dominating set in circle graphs is NP-complete. We further present an O(n((n)/(k²-k))^2k2-2k)-time algorithm for finding the minimum paired-dominating set in k-polygon graphs, a subclass of circle graphs. Additionally, we refine the existing algorithm of Elmallah and Stewart for computing the minimum dominating set in k-polygon graphs, reducing its time complexity from O(n^4k2+3) to O(n^3k-5), and further extend it to find the minimum total dominating set.

Related

• Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs
• Complexity of Paired Domination in AT-free and Planar Graphs
• Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs
• A Linear-Time Algorithm for the Weighted Paired-Domination Problem on Block Graphs
• Parameterized Domination in Circle Graphs