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

Bauer, D. and Broersma, H.J. and Kahl, N. and Morgana, A. and Schmeichel, E. and Surowiec, T. (2007) Tutte sets in graphs II: The complexity of finding maximum Tutte sets. Discrete Applied Mathematics, 155 (10). pp. 1336-1343. ISSN 0166-218X

PDF
Restricted to UT campus only: Request a copy
164Kb

Abstract:	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.
Item Type:	Article
Copyright:	© 2007 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/61771
Official URL:	http://dx.doi.org/10.1016/j.dam.2007.02.002
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241730