𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An augmenting graph approach to the stable set problem in P5-free graphs

✍ Scribed by Rodica Boliac; Vadim V. Lozin

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
149 KB
Volume
131
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

The complexity status of the stable set problem in the class of P5-free graphs is unknown.

In the present paper we study an approach to the problem based on ΓΏnding augmenting graphs. The main result is that the stable set problem in the class of P5-free graphs is polynomially equivalent to the problem of ΓΏnding augmenting graphs containing a P4. We apply this result to detect a new inΓΏnite family of graph classes where the problem has a polynomial time solution. The new family generalizes several previously known results.

πŸ“œ SIMILAR VOLUMES

P5-free augmenting graphs and the maximu
P5-free augmenting graphs and the maximum stable set problem
✍ Michael U. Gerber; Alain Hertz; David Schindl πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 174 KB

The complexity status of the maximum stable set problem in the class of P5-free graphs is unknown. In this paper, we ΓΏrst propose a characterization of all connected P5-free augmenting graphs. We then use this characterization to detect families of subclasses of P5-free graphs where the maximum stab

Polynomial algorithms for the maximum st
Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs
✍ Raffaele Mosca πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 588 KB

The Maximum Stable Set Problem (MS) is a well-known NP-hard problem. A popular research stream considers classes of graphs, defined in terms of forbidden subgraphs, in which either MS is NP-hard or can be solved by polynomial algorithms. In this paper we focus on three of these classes: in one of th