Raziskovalni matematični seminar - Arhiv

In this talk, clique trees and compatible trees are analyzed in more depth, thus strengthening the sense of duality between the two classes.

 

This work is mostly based on some chapters of my PhD thesis, under the supervision of Marisa Gutierrez.

In this talk we will briefly survey the classical algorithms from 1984 due to Hsu and Nemhauser that solve the weighted and the unweighted minimum clique cover problem on claw-free perfect graphs in O(|V(G)|^5) time, and present a very recent approach that reduces the problem to the question whether a given maximal (not necessarily maximum) stable set S, is of maximum weight. In the cardinality case, we answer this question by solving a suitable 2-SAT instance, and obtain a new combinatorial algorithm that produces both a minimum clique cover and an maximum stable set of a claw-free perfect graph G in time O(|V(G)|^3), in the spirit of the augmenting path algorithm for maximum bipartite matching and minimum vertex cover. In the weighted case, the question reduces to a kind of "weighted" 2-SAT problem. This latter problem was first solved by Schrijver in 1991 (and also Peis in 2007), and then independently considered by several people in the Constraint Programming Community, like for instance Schutt and Stuckey in 2010. We propose here a novel approach that takes advantage of the structure of the polyhedron when dealing with the minimum weight clique cover problem. It follows that a minimum weight clique cover of a claw-free perfect graph G can be found in time O(|V(G)|^3).

 

This is joint work with Gianpaolo Oriolo, Claudia Snels and Gautier Stauffer.