Weighted domination of cocomparability graphs (Q1382270)

The paper investigates weighted domination (in some variants) for the class of cocomparability graphs and the subclass of cobipartite graphs. It is shown that these problems are NP-complete for the class of cobipartite graphs when arbitrary integers as weights are allowed while all these problems can be solved in polynomial time for the larger class of cocomparability graphs if the vertex weights are integers bounded by some constant. In particular an \(O(n^2)\)-algorithm is given for the weighted independent perfect domination problem on cocomparability graphs of order \(n\).