Polynomial Time Recognition of Essential Graphs Having Stability Number Equal to Matching Number

For a graph \(G\) let \(\alpha (G)\) and \(\mu (G)\) denote respectively the cardinality of a maximum stable set and of a maximum matching of \(G\). It is well-known that computing \(\alpha (G)\) is NP-hard and that computing \(\mu (G)\) can be done in polynomial time. In particular checking if \(\alpha (G)=\mu (G)\) is NP-complete and relies on the fact that computing \(\alpha (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 \(\alpha (G) = \alpha (G[A]) + \alpha (G[B])\), where computing \(\alpha (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 \(\alpha (G)\) remains NP-hard for such graphs). This paper shows that: (i) for every essential graph \(G\), checking if \(\alpha (G)=\mu (G)\) can be done in polynomial time; (ii) essential graphs for which \(\alpha (G)=\mu (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.

Authors and Affiliations

1. Dipartimento di Economia, Università degli Studi “G. d’Annunzio”, Pescara, 65121, Italy

   Raffaele Mosca

2. Dipartimento di Matematica, Universitá del Salento, Lecce, 73100, Italy

   Paolo Nobili

Corresponding author

Correspondence to Raffaele Mosca.

Reprints and permissions