max planck institut
mpii logoMinerva of the Max Planck Society

Advanced Graph Algorithms (Summer 2012)

Basic Information

Lecture time: Monday 12:15-14:00 / Thursday 16:15-18:00
Lecture room: Room 023 (E1.4)
Lecturers: Ran Duan, Jens M. Schmidt and Magnus Wahlström
Tutorial time: Wednesday 08:30-10:00
Tutorial room: Room 023 (E1.4)
Tutors: Bernhard Schommer


This course covers advanced graph algorithms from various fields. We give also a graph-theoretic background for the problems that need it. Submission of weekly exercise solutions is due on Monday 12:00; at least 50% of the total points are necessary to be admitted to the exam at the end of the term.


Date Block Topic Lecturer Homework Scribe Notes References
Apr 16 Basics Introduction, Machine Model, Graph Data Structures, Bipartite Graphs, Eulerian Graphs Jens Notes01
N. Jasper
Apr 19 Basics Circuits & Trails, Fleury's Algorithm, Hierholzer's Algorithm Jens hw01 Notes02
B. Nyári
Apr 23 Connectivity Top. Sort, Detecting Strong Components, 2-Connectivity / 2-Edge-Connectivity Jens Notes03
M. Narang
Apr 26 Connectivity (Open) Ear Decompositions, Strong Orientations, Testing 2-(Edge-)Connectivity in Linear Time, Bipolar Orientations, s-t-Numberings + Algorithm Jens hw02 Notes04

Apr 30 Matchings Definitions, Hopcroft–Karp algorithm, Edmonds algorithm Ran (room change) Slides05 room: MMCI building, R323
May 3 Matchings Hall's Theorem, Hungarian Method for Bipartite Weighted Matchings Ran Slides06
May 7 Matchings Weighted Matchings in General Graphs, Some approximate approach Ran hw03 Slides07
May 10 Dynamic Algorithms Dynamic Connectivity and Spanning Trees in Amortized Poly-log time Ran Slides08 [6]
May 14 Dynamic Algorithms Dynamic Connectivity in Worst-case O(n½) time Ran
Slides09 [7][8][9]
May 17 No lecture (Ascension Day)
May 21 Planar Graphs Planar Separator Theorem and its Applications Ran hw04
Slides10 [10]
May 24 Planar Graphs Embeddings (combinatorial+planar), Euler's Formula, Kuratowski's Theorem, Detour to Platonic Solids Jens Notes11
P. Lutzik
May 28 No lecture (Pentecost Day)
May 31 Planar Graphs Dual Graphs, Interdigitating Trees, Half-Edge Data Structure, Decremental Dynamic Adjacency Queries Jens hw05 Notes12 [11]
June 4 Planar Graphs Adjacency Queries (con'd), Max-Cut in polynomial time Jens Notes13
P. Kolev
June 7 No lecture (Corpus Christi) hw06
June 11 Planar Graphs Max-Cut in polynomial time (con'd), Minimum Spanning Trees in linear time Jens [12][13][14]
June 14
Shortest Paths with Matrix Multiplication Ran hw07 Slides14
June 18 NP-Hard Problems Intro (FPT). Vertex Cover: FPT algorithm, Buss' kernel. Feedback Vertex Set: FPT algorithm Magnus Notes15
P. Kolev
June 21 NP-Hard Problems Kernels for Vertex Cover by Matching and for Feedback Vertex Set Magnus hw08 Notes16 (with addendum)
P. Kolev
June 25 NP-Hard Problems Hamiltonian Path Problem, k-Path, Chromatic number Magnus (room change) [19][20][21] room: MMCI building, R323
June 28 NP-Hard Problems FPT Cut Problems: Important separators, Multiway Cut Magnus hw09 [22][23]
July 2 NP-Hard Problems Treewidth: Tree decompositions, Algorithmic use (dynamic programming), Introduction to Bidimensionality Magnus [24][25]
July 5 NP-Hard Problems Planar Graphs: Linear Kernels, Bidimensionality, Subexponential Time Parameterized Algorithms Magnus hw10 See links at Wikipedia; for the kernel, see [26].
July 9 NP-Hard Problems Problems on Restricted Graph Classes Magnus
July 12 Combinatorial Algorithms for Linear Fisher Markets Ran hw11 Slides17
July 16 Research Talk Planarity Testing in Linear Time via Certificates for 3-Connected Graphs Jens Slides18 (part) [27][28][29]
July 19 Research Talk Worst-case subgraph connectivity Ran Slides19
July 23 Research Talk Representative sets and irrelevant vertices: New tools for kernelization Magnus Slides20 [30]
July 30-August 1 Exam all

Prerequisites: Basics in discrete mathematics, calculus, algorithms and complexity. At Saarland University these topics are covered in the bachelor courses Mathematik für Informatiker 1, Grundzüge der Theoretischen Informatik, and Grundzüge von Algorithmen und Datenstrukturen.
Policies: SWS: 4+2, Credit Points: 9
Exam: To be admitted to the exam, you have to achieve at least 50% of the total number of points in the tutorials. Your grade will only be dependent on the exam.

[1] J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008
[2] R. Diestel. Graph Theory. Springer, 2012. (Free preview available online)
[3] I. Wegener. A simplified correctness proof for a well-known algorithm computing strongly connected components. Inf. Process. Lett. 83:1, pp. 17-19, 2002.
[4] J. M. Schmidt. A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Manuscript.
[5] U. Brandes. Eager st-Ordering, ESA'02, pp. 247-256, 2002.
[6] J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001.
[7] G. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781–798 (1985)
[8] D. Eppstein, Z. Galil, G. Italiano, A. Nissenzweig. Sparsification – a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669–696 (1997)
[9] T. M. Chan, M. Patrascu, and L. Roditty. Dynamic connectivity: Connecting to networks and geometry. In Proceedings 49th FOCS, pages 95–104, 2008.
[10] R. Lipton, and R. Tarjan. A separator theorem for planar graphs. Siam J. Appl. Math., Vol. 36, No. 2, pages 177–189, 1979.
[11] P. Klein. Optimization Algorithms for Planar Graphs
[12] Hadlock. Finding a maximal cut of a planar graph in polynomial time, Siam J. Comp. 4 (3), pages 221-225, 1975.
[13] M. Mares. Two Linear Time Algorithms for MST on Minor Closed Graph Classes. Archivum Mathematicum (Brno), Vol. 40, pages 315-320, 2004.
[14] M. Mares. Graph Algorithms, Ph.D.-Thesis, Charles University, Prague, 2008.
[15] R. Niedermeier. Invitation to Fixed Parameter Algorithms. Oxford University Press, 2006.
[16] J. Chen, F. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74:7, pp. 1188-1198, 2008.
[17] F. Abu-Khzam, M. Fellows, M. Langston, H. Suters. Crown Structures for Vertex Cover Kernelization. Theory Comput. Syst. (MST) 41(3), pp. 411-430, 2007.
[18] S. Thomassé. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms (TALG) 6(2), 2010.
[19] A. Björklund, T. Husfeldt, M. Kiovisto. Set Partitioning via Inclusion-Exclusion. SIAM J. Comput. (SIAMCOMP) 39(2):546-563, 2009.
[20] G. Woeginger. Open problems around exact algorithms. Discrete Applied Mathematics (DAM) 156(3):397-405, 2008.
[21] N. Alon, R. Yuster, U. Zwick. Color-Coding. J. ACM (JACM) 42(4):844-856, 1995.
[22] D. Marx. Parameterized graph separation problems. Theor. Comput. Sci. (TCS) 351(3):394-406, 2006.
[23] J. Chen, Y. Liu, S. Lu. An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. Algorithmica 55(1):1-13, 2009.
[24] Tree decomposition (Wikipedia link).
[25] E. Demaine, F. Fomin, M.T. Hajiaghayi, D. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52 (6): 866–893, 2005.
[26] J. Alber, M. Fellows, R. Niedermeier. Efficient Data Reduction for DOMINATING SET: A Linear Problem Kernel for the Planar Case. SWAT 2002.
[27] J. M. Schmidt. A Planarity Test via Construction SequencesManuscript.
[28] C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. Graph Drawing (GD'00): 7790, 2001. 
[29] J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549568, 1974.
[30] S. Kratsch and M. Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. FOCS 2012 (to appear).

More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)