On a perfect graph $G(V, E)$ with a strictly positive integer
weight function on the vertices $w(v)$, $v\in V$, the minimum
weight clique cover problem is the dual problem of the maximum
weight stable set and it consists of building a collection of
cliques $\mathcal{C}$, each one with a non negative weight $y_C$,
such that, for each $v\in V$, $\sum_{C\in\mathcal{C}:v\in
C}y_C\geq w(v)$, and $\sum_{C\in\mathcal{C}}y_C$ is minimum. The
minimum weight clique cover can be solved in polynomial time on
perfect graphs with the ellipsoid method, however, for particular
classes of perfect graphs, there also exist poly-time
combinatorial algorithms.
This is the case, for instance, for claw-free perfect graphs,
where a combinatorial algorithm has been proposed by Hsu and
Nemhauser. (A graph is claw-free if none of its vertices has a
stable set of size three in its neighborhood.) To the best of our
knowledge, this is so far the only available combinatorial
algorithm to solve the problem in claw-free perfect graphs.
The algorithm in by Hsu and Nemhauser is then heavily based on the
solution of the maximum weight stable set, so, in a way, the
algorithm it is essentially a dual algorithm. In this paper, we
propose an algorithm for the minimum weight clique cover for a
relevant subclass of claw-free perfect graphs which is essentially
primal.
The algorithm exploits an algorithmic decomposition theorem by
Faenza, Oriolo and Stauffer for quasi-line graphs. A graph is
quasi-line if the neighborhood of each vertex can be covered by
two cliques. Quasi-line graphs are a generalization of line graphs
and a subclass of claw-free graphs, and it is well known that a
graph is claw-free perfect if and only if it is quasi-line
perfect.
Our new algorithm is designed for the case in which the claw-free
perfect graph $G$ is the composition of some simple graphs called
strips. We are now dealing with the remaining case, that is a
subclass of quasi-line net-free perfect graphs. |