MATH/CS/ISYE 7510 Graph Algorithms

This is an optional class in the PhD program in Algorithms, Combinatorics and Optimization. The objective is to provide rigorous treatment of Graph Algorithms at the level of an advanced graduate course. You need to know Graph Theory at least at the level of MATH 6014, and you need to know some algorithmics, say at the level of CS 6550. You will also need the mathematical sophistication of a second-year mathematics graduate student in order to succeed in the course.

This will be a theoretical course. There will be no implementation requirements. You will be required to design various algorithms and rigorously prove their correctness and estimate their running time. You will also be required to prove theorems relevant to the design of efficient algorithms. 

Instructor: Robin Thomas

Textbook: None. I have not found a suitable book. References will be provided.

Some texts you may wish to consult:
Diestel, Graph Theory
Bollobas, Modern Graph Theory
West, Introduction to Graph Theory
Bondy and Murty, Graph Theory
Even, Graph Algorithms
Golumbic, Algorithmic Graph Theory and Perfect Graphs
Cook, Cunningham, Pulleyblank and Schrijver, Combinatorial Optimization

Possible topics: 
*Connectivity: Vertex- and edge-disjoint paths in graphs, the disjoint 2 paths problem, testing connectivity, decomposing a graph into 3-connected components (Tutte's cleavage units) in linear time, edge-disjoint spanning trees, edge-connectivity, splitting off vertices, Gomory-Hu trees, tangles and brambles in graphs and the canonical tree-decomposition they generate, connectivity augmentation
*Matching: Review of Edmonds' blossom algorithm and Edmonds' matching polyhedron theorem, the Chinese postman problem, T-cuts and T-joins, Pfaffian orientations and their applications
*Coloring: Schrijver's bipartite edge-coloring algorithm, 5-coloring planar graphs in linear time, choosability
*Testing planarity: A linear-time planarity test, testing embeddability in surfaces
*Perfect graphs: Basic properties, recognition, optimization on perfect graphs, applications
*Graph classes: Interval graphs, chordal graphs, split graphs, permutation graphs, threshold graphs, comparability graphs, intersection graphs of geometric objects. Properties, recognition and optimization.
*Directed graphs: Testing connectivity of digraphs, splitting off vertices, connectivity augmentation, disjoint directed cycles, even cycles, disjoint branchings, the Lucchesi-Younger theorem
*Tree-width: Basic properties, linear-time algorithms for problems on graphs of bounded tree-width, applications
*Separators: The Lipton-Tarjan separator theorem, separators in graphs with an excluded minor, applications
*Graph Minors: The Graph Minor Theorem, The disjoint paths algorithm, polynomial-time algorithms for various problems when the input graph excludes a certain minor

Grades: Each student will be required to scribe several lectures. A combination of homework, exam, and a presentation (in class, in a seminar or in private).

Final exam. Due before 3:05PM, April 29, 2009.

Office hours: MW 2-3 and by appointment.

Office: 217B Skiles.

Lecture archive: 

January 7: Introduction to Pfaffian orientations. Handout was provided.
January 12: Edmonds' blossom algorithm to find a maximum matching. See Cook at al.
January 14: Finding minimum weight perfect matchings. See Cook at el. Notes (unchecked)
January 21: Edmonds' polyhedron theorem, tight cuts, the linear hull of perfect matchings, bricks and braces
January 26: Solutions to exercises, the dimension of the linear hull of perfect matchings. Notes (unchecked)
January 28: Dimension of the linear hull of perfect matching, Lovasz' theorem that the list of bricks and braces does not depend on the tight cuts chosen. Here are old notes regarding the former, and here are my notes on Matching decomposition.
February 2: Polynomial-time equivalence of deciding whether a graph has a Pfaffian orientation and whether a given orientation is Pfaffian. See earlier handout "Origins of Pfaffian orientations".
February 4: Polya's permanent problem, even directed cycles and even digraphs. Here is first part of Chapter 3.
February 9: Trading bananas, sign-nonsingular matrices, and the even permutation polytope. Here is the second part of Chapter 3.
February 11: Minimally non-2-colorable hypergraphs. Handout given in class.

March 30: The Lipton-Tarjan separator theorem
April 1: A separator theorem for graphs with no K_h minor
April 6: A separator theorem for graphs with no K_h minor
April 8: Applications of the separator theorem
April 13: A simple quadratic planarity algorithm
April 15: A linear-time planarity algorithm
April 20: A linear-time planarity algorithm