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

Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
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
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 241730