Minimum weighted clique cover on claw-free perfect graphs

BONOMO, FLAVIA; ORIOLO, GIANPAOLO; SNELS, CLAUDIA

JOURNAL OF GRAPH THEORY

JOHN WILEY & SONS INC

Lugar: New York; Año: 2021 vol. 96 p. 231 - 268

0364-9024

The first combinatorial algorithm for the minimum weighted clique cover (MWCC) in a claw-free perfect graph $G$ due to Hsu and Nemhauser dates back to 1984. It is essentially a ``dual´´ algorithm as it relies on any algorithm for the maximum weighted stable set (MWSS) problem in claw-free graphs and, taking into account the best known complexity for the latter problem, its complexity is $O(|V(G)|^{5})$. More recently, Chudnovsky and Seymour introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well. In this paper, we show that a MWCC of a perfect strip-composed graph, with the basic graphs belonging to a class ${cal G}$, can be found in polynomial time, provided that the mwcc problem can be solved on ${cal G}$ in polynomial time. For the case of claw-free perfect strip-composed graphs, the algorithm can betailored so that it never requires the computation of a MWSS on the strips and can be implemented as to run in $O(|V(G)|^{3})$ time. Finally, building upon several results from the literature, we show how to deal with non-strip-composed claw-free perfect graphs, and therefore compute a MWCC in a general claw-free perfect graph in $O(|V(G)|^{3})$ time.