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


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 K1,4 as an induced subgraph. Our results provide a dichotomy for K1,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


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


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 (Xs, Ys) with the
property that each dissimilar pair of nodes z, y in N(s) is adjacent
if and only if both belong to Xs or Ys. 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.


  Payday Loans In Michigan. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.