On the Complexity of Computing a Maximum Acyclic Matching in Undirected Graphs

Samer Nofal ()
Additional contact information
Samer Nofal: Department of Computer Science, German Jordanian University, Amman 11180, Jordan

Mathematics, 2025, vol. 13, issue 5, 1-12

Abstract: 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 O ( ln m ) in expectation. Consequently, employing a recursive computation of a maximum acyclic matching in a given graph, if the recursion depth meets the expectation O ( ln m ) , then a maximum acyclic matching can be computed in time O ( n 3.4 ) and space O ( m ln m ) . However, for the general case, the complexity of the recursive computation of a maximum acyclic matching is in O ( n 2 2 m ) time and in O ( m 2 ) space.

Keywords: maximum acyclic matching; undirected graph; recursive algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/5/889/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/5/889/ (text/html)

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:gam:jmathe:v:13:y:2025:i:5:p:889-:d:1607029

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().