On the Complexity of Computing a Maximum Acyclic Matching in Undirected Graphs - Samer Nofal (Mathematics, 2025)
The problem of finding a maximum acyclic matching in a simple undirected graph is known to be NP-complete. In this paper, we present new results; we show that a maximum acyclic matching in a given undirected graph (with n vertices and m edges) can be computed recursively with a recursion depth <semantics>O(lnm)</semantics> in expectation. Consequently, employing a recursive computation of a maximum acyclic matching in a given graph, if the recursion depth meets the expectation <semantics>O(lnm)</semantics>, then a maximum acyclic matching can be computed in time <semantics>O(n3.4)</semantics> and space <semantics>O(mlnm)</semantics>. However, for the general case, the complexity of the recursive computation of a maximum acyclic matching is in <semantics>O(n22m)</semantics> time and in <semantics>O(m2)</semantics> space.