Acyclic domination on bipartite permutation graphs

For a graph G=(V,E), a subset S⊆V is called an acyclic dominating set of G if every vertex in V−S is adjacent to at least one vertex in S and the subgraph induced by S contains no cycles. In this paper, we present a linear time algorithm for transforming a minimum dominating set in a bipartite permutation graph into a minimum acyclic dominating set. Chao et al. gave a linear time algorithm to find a minimum dominating set of a permutation graph. Thus, we show that the acyclic domination problem is linear time solvable for bipartite permutation graphs.