On some hard and some tractable cases of the maximum acyclic matching problem

M. Fürst () and D. Rautenbach ()
Additional contact information
M. Fürst: Ulm University
D. Rautenbach: Ulm University

Annals of Operations Research, 2019, vol. 279, issue 1, No 11, 300 pages

Abstract: Abstract Three well-studied types of subgraph-restricted matchings are induced matchings, uniquely restricted matchings, and acyclic matchings. While it is hard to determine the maximum size of a matching of each of these types, whether some given graph has a maximum matching that is induced or has a maximum matching that is uniquely restricted, can both be decided efficiently. In contrast to that we show that deciding whether a given bipartite graph of maximum degree at most four has a maximum matching that is acyclic is NP-complete. Furthermore, we show that maximum weight acyclic matchings can be determined efficiently for $$P_4$$ P 4 -free graphs and $$2P_3$$ 2 P 3 -free graphs, and we characterize the graphs for which every maximum matching is acyclic.

Keywords: Matching; Induced matching; Uniquely restricted matching; Acyclic matching (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03311-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:279:y:2019:i:1:d:10.1007_s10479-019-03311-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03311-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().