Minimum weight clique cover in claw-free perfect graphs

2014-10-06

10:00-11:00

FAMNIT-SEMIN

Dr. Flavia Bonomo (Buenos Aires University, Argentina)

For a perfect graph G, and given a weight function w on the vertices of G, linear programming duality ensures that the weight of a minimum weighted clique cover (an assignment of a non-negative weight y_C to each clique C of G, such that, each vertex v is covered by cliques whose weight sums at least w(v) and that
minimizes the total sum of the weights of the cliques) is the same as the weight of a maximum weighted stable set (a set of pairwise nonadjacent vertices S that maximizes the sum of the weights). Moreover Grötschel, Lovász and Schrijver gave in 1988 a (non combinatorial) algorithm, building upon Lovász’s theta function, to compute both solutions. It is a major open problem in combinatorial optimization whether there exist polynomial time combinatorial algorithms for those two problems. For particular classes of perfect graphs, such algorithms exist. This is the case, for instance, for claw-free perfect graphs (a graph is claw-free if none of its vertices has a stable set of size three in its neighborhood).

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.

Minimum weight clique cover in claw-free perfect graphs

Download slides.