A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs

• Maximum weight independent set on cocomparability graphs.
• Linear time algorithm, does not compute the complement or the corresponding poset.
• Algorithm exploits the vertex ordering characterization of cocomparability graphs.
• Linear time minimum weight vertex cover for cocomparability graphs as a corollary.

The maximum weight independent set (WMIS) problem is a well-known NP-hard problem. It is a generalization of the maximum cardinality independent set problem where all the vertices have identical weights. There is an O(n2)O(n2) time algorithm to compute a WMIS for cocomparability graphs by computing a maximum weight clique on the corresponding complement of the graph [1]. We present the first O(m+n)O(m+n) time algorithm to compute a WMIS directly on the given cocomparability graph, where m and n are the number of edges and vertices of the graph respectively. As a corollary, we get the minimum weight vertex cover of a cocomparability graph in linear time as well.