Recent Developments in Theoretical Computer Science.

The course aims at covering some of the recent topics that are of interest in research in graph algorithms with a focus on graph matchings and dynamic graph algorithms. The course will be structured into three broad themes. In each theme, we will first build the foundation by studying some classical results and then move on to recent research results.

Instructor: Meghana Nasre.

Slot: E.
Course Number: CS6190.

• Matching algorithms: The question of finding matchings in graphs has a rich history dating from the early algorithms of Hopcroft and Karp for bipartite matching and Edmonds famous blossom shrinking algorithm which is widely considered as a breakthrough result. Here, we will first study classical results like Hopcroft Karp, Edmonds Algorithm, and algorithms for weighted bipartite matchings. We will then look at the Dulmage Mehdelson Decomposition, Gallai Edmonds Decomposition and then move to recent results like improved algorithms for matchings in regular bipartite graphs, improved algorithms for matchings in general graphs with small weights.


• Algorithmics of Matchings with Preferences: Matching problems under preferences arise in many real-world scenarios. Here we start with the stable marriage problem, the lattice structure of the stable marriage problem, stable roommates problem. We will then move to other notions of optimality like rank-maximality, popularity and related recent results. The heading of this theme based on a recent book by David Manlove titled Algorithmics of Matchings with Preferences. An earlier book by Gusfield and Irving titled Stable Marriage -- Structure and Algorithms along with the recent book will serve as good references.


• Dynamic Graph algorithms: Change is the only thing that is constant -- this is more than true in case of graphs derived out of several applications like communication networks, social networks etc. In this theme we study algorithms that maintain a graph property efficiently after an update. The properties that we will consider are connectivity, shortest paths, transitive closure, and matchings. We will focus on some common tools like, clustering, graph partitioning which are useful in several dynamic algorithms. Further, we will also look at useful data structures like link-cut trees, topology trees, Euler tour trees which are useful in this context.

• Matching Theory -- by Lovasz and Plummer.
• Stable Marriage -- Structure and Algorithms -- by Rob Irving and Dan Gusfield.
• Algorithmics of Matchings under Preferences -- by David Manlove.