Abstract

For a graph G let α(G) and μ(G) denote respectively the cardinality of a maximum stable set and of a maximum matching of G. It is well-known that computing α(G) is NP-hard and that computing μ(G) can be done in polynomial time. In particular checking if α(G)=μ(G) is NP-complete and relies on the fact that computing α(G) is NP-hard (Mosca, Graphs Combinat 18:367–379, 2002). A well known result of Hammer et al. (SIAM J Alg Disc Math 3(4):511–522, 1982). states that the vertex-set of a graph G can be efficiently and uniquely partitioned in two subsets (possibly empty) A and B, such that G[A] has the König-Egerváry property while G[B] can be covered by pairwise disjoint edges and odd cycles: furthermore, one has α(G)=α(G[A])+α(G[B]), where computing α(G[A]) can be done in polynomial time. For that let us call essential those graphs which can be covered by pairwise disjoint edges and odd cycles (in particular computing α(G) remains NP-hard for such graphs). This paper shows that: (i) for every essential graph G, checking if α(G)=μ(G) can be done in polynomial time; (ii) essential graphs for which α(G)=μ(G) can be recognized in polynomial time and for such graph a maximum stable set can be computed in polynomial time; (iii) a new characterization of graphs which have the König-Egerváry property can be derived in that context.

Autore Pugliese

• Nobili Paolo

Tutti gli autori

• Mosca R. , Nobili P.

Titolo volume/Rivista

GRAPHS AND COMBINATORICS

Anno di pubblicazione

2015

ISSN

0911-0119

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

1

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile