An O(n)O(n)-time algorithm for the paired domination problem on permutation graphs

A vertex subset DD of a graph GG is a dominating set if every vertex of GG is either in DD or is adjacent to a vertex in DD. The paired domination problem on GG asks for a minimum-cardinality dominating set SS of GG such that the subgraph induced by SS contains a perfect matching; motivation for this problem comes from the interest in finding a small number of locations to place pairs of mutually visible guards so that the entire set of guards monitors a given area. The paired domination problem on general graphs is known to be NP-complete.In this paper, we consider the paired domination problem on permutation graphs. We define an embedding of permutation graphs in the plane which enables us to obtain an equivalent version of the problem involving points in the plane, and we describe a sweeping algorithm for this problem; if the permutation over the set Nn={1,2,…,n}Nn={1,2,…,n} defining a permutation graph GG on nn vertices is given, our algorithm computes a paired dominating set of GG in O(n)O(n) time, and is therefore optimal.