## Invited Session Fri.1.H 3008

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

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

### Algorithms in claw-free graphs

**Chair: Gautier Stauffer**

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

**Erik Jan van Leeuwen**

Domination when the stars are out - Efficient decomposition of claw-free graphs

**Coauthors: Danny Hermelin, Matthias Mnich, Gerhard Woeginger**

**Abstract:**

We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are not fixed-parameter tractable on the slightly larger class of graphs that exclude *K*_{1,4} as an induced subgraph. Our results provide a dichotomy for *K*_{1,L}-free graphs and characterize when the problems are fixed-parameter tractable.

**Friday, 11:00 - 11:25 h, Room: H 3008, Talk 2**

**Yuri Faenza**

Separating stable sets in claw-free graphs through extended formulations

**Coauthors: Gianpaolo Oriolo, Gautier Stauffer**

**Abstract:**

The stable set polytope in claw-free graphs (ssp-cf) is a well-known generalization of the matching polytope. A linear description of the latter only requires rank inequalities (i.e., with 0/1 coefficients), while the associated separation problem can be solved via a purely combinatorial routine. For ssp-cf the situation is quite different: no complete description is known, and there exist examples of facets with arbitrarily high coefficients. Moreover, the only known separation routine relies on the ellipsoid method.

In this talk, we provide linear programming extended formulations for ssp-cf, together with polynomial time separation routines for those formulations (they are not compact). Those formulations rely on combinatorial optimization, polyhedral combinatorics, and structural graph theory results. We then exploit one of those extended formulations to propose a new polytime algorithm for solving the separation problem for ssp-cf. This routine combines the separation algorithm for the matching polytope and the solution of (moderate size) compact linear programs, hence it does not require the application of the ellipsoid method.

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

**Paolo Nobili**

A decomposition algorithm for the weighted stable-set problem in claw-free graphs

**Coauthor: Antonio Sassano**

**Abstract:**

In this paper we describe a new characterization of a *line-graph*

*G(V, E)* in terms of forbidden substructures. Unlike the classical

characterization due to Bermond and Meyer based on forbidden induced

subgraphs, we rely upon the properties of a suitable maximal stable set

*S* of *G*. Following Lozin, we say that two nodes *u* and *v* in *V*

\ S are *similar* if *N(u) ∩ S = N(v) ∩ S*.

Moreover, extending a definition due to Schrijver, we say that a node *s*

∈ S is *clique-splittable* in *G* with respect to *S* if the

nodes in *N(s)* can be partitioned in two cliques *(X*_{s}, Y_{s}) with the

property that each dissimilar pair of nodes *z, y* in *N(s)* is adjacent

if and only if both belong to *X*_{s} or *Y*_{s}. Our main result is that a

claw-free graph *G* is a line graph if and only if each node *s ∈ S*

is clique-splittable and *S* does not define two special structures in

*G*, namely a pair of *cross-linked* nodes or a *free-strip*.