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

Description

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.

Lectures

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	[1][2]
Apr 19	Basics	Circuits & Trails, Fleury's Algorithm, Hierholzer's Algorithm	Jens	hw01	Notes02 B. Nyári	[W1][W2][1]
Apr 23	Connectivity	Top. Sort, Detecting Strong Components, 2-Connectivity / 2-Edge-Connectivity	Jens		Notes03 M. Narang	[3][1]
Apr 26	Connectivity	(Open) Ear Decompositions, Strong Orientations, Testing 2-(Edge-)Connectivity in Linear Time, Bipolar Orientations, s-t-Numberings + Algorithm	Jens	hw02	Notes04	[4][5][2]
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	[11]
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	[11][12]
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	[15][16]
June 21	NP-Hard Problems	Kernels for Vertex Cover by Matching and for Feedback Vertex Set	Magnus	hw08	Notes16 (with addendum) P. Kolev	[17][18]
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 Sequences. Manuscript.
[28]	C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. Graph Drawing (GD'00): 77–90, 2001.
[29]	J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549–568, 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