Testing Maximum Matching Solvers in d-Partite Graphs

This paper presents a comprehensive framework for testing and evaluating maximum matching algorithms in bipartite and d-partite graphs. The framework addresses both accuracy and efficiency through structured test generation techniques, utilizing a standardized file format for consistent graph representation across solvers. We introduce multiple test case generation methods, including random bipartite graph creation verified via the Hopcroft-Karp algorithm, perfect matching construction for d-partite graphs, and a dimension restriction technique that strategically constructs graphs with known solutions. Given the inherent complexity of NP-hard problems, our approach integrates automated verification through Integer Programming solvers and exhaustive backtracking algorithms. Comparative analysis of different solvers reveals performance variations across graph structures and densities, while also highlighting limitations related to implementation constraints and integer programming diversity. This framework provides a rigorous foundation for evaluating maximum matching algorithms, offering insights into their strengths across various computational scenarios.