Tutte sets in graphs II: The complexity of finding maximum Tutte sets

∗Part of this research was done while the first two authors were visiting the Universita ́ di Roma. The hospitality and financial support are gratefully acknowledged. 1 A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V (G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs