On domination problems for permutation and other graphs (Q1100915)

The authors study various restrictions on NP-complete graph problems to subclasses of perfect graphs. Specifically, the following problems are considered: (a) weighted independent domination problem for permutation graphs, (b) weighted feedback vertex set problem for permutation graphs, (c) weighted dominating clique problem for several classes of graphs. Polynomial time algorithms are obtained for (a) and (b), \(O(n^ 2)\) and \(O(n^ 6)\), respectively. In the case of (c), the authors obtain an NP- completeness result for weakly triangulated graphs as well as polynomial time bounds for other families of graphs.