max planck institut

informatik

informatik

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 |
[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). |