Engineering Advanced (Hyper)graph b-matching Algorithms

• Applicant: Professor Dr. Christian Schulz
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 543787284

This project aims to develop highly scalable algorithms for the general problem of finding b-matchings in hypergraphs. Researchers have recently extended the concept of matchings in graphs to more general problems such as matchings or b-matchings in hypergraphs broadening the scope of potential applications and challenges. While the maximum matching problem in graphs can be solved in polynomial time, it is NP-complete in hypergraphs. Still in practice, fast and scalable approximation/exact algorithms are required to handle large and complex inputs. Currently, there are no scalable (parallel) algorithms for the hypergraph b-matching problem available. The goal of the project is to devise and engineer highly scalable algorithms for a range of hypergraph b-matching problems, pushing the boundaries in terms of parallelization as far as possible, and making the algorithms useful for existing libraries, interfaces, and applications. The resulting algorithms and implementations will be more robust, flexible, and scalable to large parallel machines and application instances much larger than previously possible. The most successful implementations will be provided as easy-to-use, open-source software.

• DFG Programme: Research Grants