Stable set problems subsume matching problems since a matching is a stable set in a so- called line graph but stable set problems are hard in general while matching can be solved efficiently [11]. However, there are some classes of graphs where the stable set problem can be solved efficiently. A famous class is that of claw-free graphs; in fact, in 1980 Minty [19, 20] gave the first polynomial time algorithm for finding a maximum weighted stable set (mwss) in a claw-free graph. One of the reasons why stable set in claw-free graphs can be solved efficiently is because the so called augmenting path theorem [4] for matching generalizes to claw-free graphs [5] (this is what Minty is using). We believe that another core reason is structural and that there is a intrinsic matching structure in claw-free graphs. Indeed, recently Chudnovsky and Seymour [8] shed some light on this by proposing a decomposition theorem for claw-free graphs where they describe how to compose all claw-free graphs from building blocks. Interestingly the composition operation they defined seems to have nice consequences for the stable set problem that go much beyond claw-free graphs. Actually in a recent paper [21] Oriolo, Pietropaoli and Stauffer have revealed how one can use the structure of this composition to solve the stable set problem for composed graphs in polynomial time by reduction to matching. In this paper we are now going to reveal the nice polyhedral counterpart of this composition procedure, i.e. how one can use the structure of this composition to describe the stable set polytope from the matching one and, more importantly, how one can use it to separate over the stable set polytope in polynomial time. We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph G, we show two integral extended formulation for STAB(G) and a procedure to separate in polynomial time over STAB(G); moreover, we provide a complete characterization of STAB(G) when G is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins. We believe that the missing bricks towards the characterization of the stable set polytope of claw-free graphs are more technical than fundamentals; in particular, we have a characterization for most of the building bricks of the Chudnovsky-Seymour decomposition result and we are therefore very confident it is only a question of time before we solve the remaining case.

Faenza, Y., Oriolo, G., Stauffer, G. (2010). The hidden matching-structure of the composition of strips: a polyhedral perspective [Working paper].

The hidden matching-structure of the composition of strips: a polyhedral perspective

ORIOLO, GIANPAOLO;
2010-01-01

Abstract

Stable set problems subsume matching problems since a matching is a stable set in a so- called line graph but stable set problems are hard in general while matching can be solved efficiently [11]. However, there are some classes of graphs where the stable set problem can be solved efficiently. A famous class is that of claw-free graphs; in fact, in 1980 Minty [19, 20] gave the first polynomial time algorithm for finding a maximum weighted stable set (mwss) in a claw-free graph. One of the reasons why stable set in claw-free graphs can be solved efficiently is because the so called augmenting path theorem [4] for matching generalizes to claw-free graphs [5] (this is what Minty is using). We believe that another core reason is structural and that there is a intrinsic matching structure in claw-free graphs. Indeed, recently Chudnovsky and Seymour [8] shed some light on this by proposing a decomposition theorem for claw-free graphs where they describe how to compose all claw-free graphs from building blocks. Interestingly the composition operation they defined seems to have nice consequences for the stable set problem that go much beyond claw-free graphs. Actually in a recent paper [21] Oriolo, Pietropaoli and Stauffer have revealed how one can use the structure of this composition to solve the stable set problem for composed graphs in polynomial time by reduction to matching. In this paper we are now going to reveal the nice polyhedral counterpart of this composition procedure, i.e. how one can use the structure of this composition to describe the stable set polytope from the matching one and, more importantly, how one can use it to separate over the stable set polytope in polynomial time. We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph G, we show two integral extended formulation for STAB(G) and a procedure to separate in polynomial time over STAB(G); moreover, we provide a complete characterization of STAB(G) when G is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins. We believe that the missing bricks towards the characterization of the stable set polytope of claw-free graphs are more technical than fundamentals; in particular, we have a characterization for most of the building bricks of the Chudnovsky-Seymour decomposition result and we are therefore very confident it is only a question of time before we solve the remaining case.
Working paper
2010
Rilevanza internazionale
Settore ING-IND/35 - INGEGNERIA ECONOMICO-GESTIONALE
English
Faenza, Y., Oriolo, G., Stauffer, G. (2010). The hidden matching-structure of the composition of strips: a polyhedral perspective [Working paper].
Faenza, Y; Oriolo, G; Stauffer, G
Altro
File in questo prodotto:
File Dimensione Formato  
frontespizio_16.pdf

accesso aperto

Descrizione: Titlepage
Dimensione 77.95 kB
Formato Adobe PDF
77.95 kB Adobe PDF Visualizza/Apri
RR-16.10.pdf

accesso aperto

Descrizione: Full text
Dimensione 349.24 kB
Formato Adobe PDF
349.24 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/7961
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact