The maximum acyclic matching problem

Abstract

The aim of this thesis is to develop exact and heuristic methods to solve the Maximum Acyclic Matching problem, which deals with obtaining maximum matching such that the subgraph induced by saturated vertices is acyclic. The maximum matching problem tries to find the most extensive possible matching set. it is a well-studied problem that can be solved with combinatorial algorithms. However, for the maximum acyclic matching problem, we are searching for not only a maximum size matching but also we require that the subgraph induced by saturated vertices does not contain any cycles. For this purpose, an additional acyclicity constraint is needed. Even though some exact and approximate algorithms are established for particular graph classes, there is no such algorithm applicable for general graphs to find a maximum acyclic matching. In this study, four algorithms are suggested. Randomly generated graphs with different density levels and sizes are used to analyze their performance. Two of the algorithms are exact algorithms, which are extensive and cutting plane formulations. Based on experimental results, the cutting plane approach performs better since it works also with larger graphs. The other two algorithms are heuristics, which are modification and construction approaches. It is observed that the construction approach performs better than the modification approach in terms of both time efficiency and quality. The construction approach yields feasible and close-to-optimal results in a shorter period. When the results of the best exact and heuristics are compared, the cutting plane algorithm performs better based on optimality. However, it is not applicable for large graphs compared to the construction algorithm. Additionally, it is seen that the effect of acyclicity constraint is increasing while graph size and density are getting larger.