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

2017/10/23 by Fürst, M., Rautenbach, D. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1710.08236

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₄-free graphs and 2P₃-free graphs, and we characterize the graphs for which every maximum matching is acyclic.

Cited by

• A Parameterized Perspective on Uniquely Restricted Matchings

Related

• Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Acyclic matchings in graphs of bounded maximum degree
• Some bounds on the uniquely restricted matching number
• On the hardness of deciding the equality of the induced and the uniquely\n restricted matching number