Paired-domination Problem on Circle and $k$-polygon Graphs

A vertex set $D \subseteq 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(n(\frac{n}{k^2-k})^{2k^2-2k})$-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~[\emph{E.S.~Elmallah and L.K.~Stewart, Independence and domination in polygon graphs, Discrete Appl. Math., 1993}] and reduce their time-complexity from $O(n^{4k^2+3})$ to $O(n(\frac{n}{k^2-k})^{2k^2-4k})$.