## Contributed Session Fri.1.H 3012

#### Friday, 10:30 - 12:00 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Cliques, stable sets, and perfect graphs

**Chair: Claudia Snels**

**Friday, 10:30 - 10:55 h, Room: H 3012, Talk 1**

**Maribel Jessica Montenegro**

On the *N*-index of the stable set polytope related to antiwebs

**Abstract:**

In this work we investigate the application of the *N* and *N*_{+} operators, defined by LovĂˇsz and Schrijver (1990), to the edge relaxation of the stable set polytope related to antiwebs. The first immediate result is that these polytopes have *N*_{+}-index equal to *1*.

Moreover, we have proved that if an antiweb *\overline{W}*_{n}^{k} is such that *n=qn'+1* and *k=q(k'+1)-1* with *n',k',q ∈ ***N** and *q ≥ 2*, it contains a subantiweb which is isomorphic to the antiweb *\overline{W}*_{n'}^{k'} and the rank constraint of this subantiweb can be used to generate the rank constraint of *\overline{W}*_{n}^{k}. Using this construction we obtain upper-bounds on the *N*-index for some particular classes of antiwebs.

**Friday, 11:30 - 11:55 h, Room: H 3012, Talk 3**

**Claudia Snels**

Minimum weighted clique cover on strip-composed perfect graphs

**Coauthors: Flavia Bonomo, Gianpaolo Oriolo**

**Abstract:**

On a perfect graph *G* where a non negative weight function on the vertices *w:V → ***R**^{+} is given, the *minimum weighted clique cover* problem ({MWCC}), consists on finding a collection of cliques **C**, each one with a non-negative value *y*_{C}, such that for every vertex *v* *∑*_{C ∈ C}**:v ∈ C**y_{C} ≥ w(v) and the weight *∑*_{C ∈ C}y_{C} is minimum.

The only available combinatorial algorithm for the {MWCC} in claw-free perfect graphs is due to Hsu and Nemhauser and dates back to 1984. More recently, Chudnovsky and Seymour in 2005 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 *G*, can be found in polynomial time, provided that the {MWCC} problem can be solved on *G* in polynomial time. We also design a new, more efficient, combinatorial algorithm for the {MWCC} problem on strip-composed claw-free perfect graphs.