Project title: Alternating paths and matchings in graphs
Name of supervisor: Dr Andrei Gagarin
Code: AG2122A
Project Description:
Background
Matchings play an important role in graph theory and applications, for example, in assignment problems, where pairs of items are to be matched together (e.g. if people are to be assigned to jobs). The problem of finding a maximum (by cardinality) matching in a given graph G=(V,E) is solvable in polynomial time. The Hungarian algorithm allows us to find a maximum-size matching in a bipartite graph, and the Edmonds’ blossoms algorithm extends the ideas of efficient usage of alternating paths to non-bipartite graphs. A variation of the problem consists in finding a smallest weight/cost maximum matching in weighted graphs.
Objectives
The objectives of this project consist in studying literature related to the theory of matchings and alternating paths in graphs, their applications, and the Hungarian algorithm and the Edmonds’ blossoms algorithm to find a maximum matching in a graph. The student will need to implement the Hungarian algorithm and run experiments on either artificially generated or some real-world instances of the problem. Another objective is to study the Edmonds’ blossoms algorithm and to understand the proof of its correctness. The minimum/maximum cost maximum-size matchings in weighted graphs and integer linear problem formulations are to be considered as well.
Approach
Study of literature on alternating paths and matchings from the points of view of Graph Theory, algorithms, and applications. Implementing the Hungarian algorithm and running computational experiments on some artificially generated or real-world instances and comparing the computational outcomes. Considering maximum-size matchings in weighted graphs and integer linear programming formulations of the problems, using generic LP/IP solvers.
References:
1. W.L. Kocay, D.L. Kreher, Graphs, Algorithms, and Optimization, 2nd ed., CRC Press, 2017, Chapter 9.
2. D. Karapetyan, A.J. Parkes, G. Gutin, A. Gagarin, Pattern-based approach to the workflow satisfiability problem with user-independent constraints, Journal of Artificial Intelligence Research 66 (2019), pp. 85-122.
3. W.L. Winston, Operations Research: applications and algorithms, 4th ed., Thomson-Brooks/Cole, 2004, Section 7.5.3.
Deliverables
A report (dissertation/thesis) and software implementing the Hungarian algorithm to solve the problem in weighted and/or unweighted graphs, together with problem instances used in computational experiments.
Prerequisites
An interest in and some knowledge of graph theory, modeling of real-life problems on graphs, as well as some computer programming skills using data structures to solve problems on graphs and combinatorial structures.