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

D. Bauer, Haitze J. Broersma, N. Kahl, A. Morgana, E. Schmeichel, T. Surowiec

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
89 Downloads (Pure)

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.
Original languageEnglish
Article number10.1016/j.dam.2007.02.002
Pages (from-to)1336-1343
Number of pages8
JournalDiscrete applied mathematics
Volume155
Issue number4542/10
DOIs
Publication statusPublished - 15 May 2007

Keywords

  • Extreme set
  • Tutte set
  • Deficiency
  • (Perfect) matching
  • D-graph

Fingerprint Dive into the research topics of 'Tutte sets in graphs II: The complexity of finding maximum Tutte sets'. Together they form a unique fingerprint.

Cite this