Weighted independent perfect domination on cocomparability graphs (Q1917231)

Let \(G = (V,E)\) be a graph in which every vertex \(v \in V\) is associated with a cost \(c(v)\). A graph is cocomparability graph if its vertex set has a cocomparability ordering, which is a labelling of \(V\) with \(1,2, \dots, n\) such that \[ i < j < k \quad \text{and} \quad (i,k) \in E \quad \text{imply} \quad (i,j) \in E \quad \text{or} \quad (j,k) \in E. \] In this paper, the authors study the problem of finding a subset \(D\) of \(V\) such that every vertex in \(V\) is equal or adjacent to exactly one vertex in \(D\) and \(\sum_{v \in D} c(v)\) is minimized. They give an \(O(|V |\cdot |E |)\) algorithm for the problem on cocomparability graphs. The algorithm can be modified slightly to run in \(O(|V |^{2.37})\) time. With some modifications, the algorithm can be adapted to take \(O(|V |+ |E |)\) time on interval graphs, which are special cocomparability graphs.