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

摘要

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 showthatmaximum weight acyclic matchings can be determined efficiently for P-4-free graphs and 2P(3)-free graphs, and we characterize the graphs for which every maximum matching is acyclic.