Paired-domination Problem on Circle and k-polygon Graphs

A vertex set D ⊆ V is considered a dominating set of G if every vertex in V − D is adjacent to at least one vertex in D. We called a dominating set D as a paired-dominating set if the subgraph of G induced by D contains a perfect matching. In this paper, we show that determining the minimum paired-dominating set on circle graphs is NP-complete. We further propose an $O\left( {n{{\left( {\frac{n}{{{k^2} - k}}} \right)}^{2{k^2} - 2k}}} \right)$-time algorithm for k-polygon graphs, a subclass of circle graphs, for finding the minimum paired-dominating set. Moreover, we extend our method to improve the algorithm for finding the minimum dominating set on k-polygon graphs in [E.S. Elmallah and L.K. Stewart, Independence and domination in polygon graphs, Discrete Appl. Math., 1993] and reduce their time-complexity from $O\left( {{n^{4{k^2} + 3}}} \right)$ to $O\left( {n{{\left( {\frac{n}{{{k^2} - k}}} \right)}^{2{k^2} - 4k}}} \right)$.