Logic in Computer Science Prof. Dr. Martin Grohe

News

Introduction

Many real world problems can be modeled as graph theoretical problems. This course will present algorithmic methods for solving various of these problems, such as finding maximum matchings, graph colorings, vertex covers and maximum cuts. Several graph theoretical topics will be treated, with an emphasis on their application in designing efficient algorithms.

In previous courses, for several graph problems efficient (polynomial time) algorithms have been presented (such as finding shortest paths and maximum flows). This course will start by studying other problems that can be solved in polynomial time, such as finding maximum matchings.

However, many problems are NP-hard, and no polynomial time algorithms should be expected for them. The first approach for such problems is to study them on restricted graph classes. In this context, graph classes such as bipartite graphs, planar graphs, graphs of bounded tree width, and perfect graphs will be treated, and algorithmic methods for them will be explained. Secondly, approximation algorithms will be presented for several problems.

Lectures will be given in English.

Contents

1. Introduction:
   1. Organization, goals, and motivation (slides)
   2. Basic definitions: graph theory (slides)
   3. Basic definitions: analysis of algorithms (slides)
   
   1. Data structures and graph representations
   2. Example: shaving a graph in linear time
   3. Example: constructing a DFS tree in linear time
2. 4. Connectivity in graphs: (slides)
   - 4.1 Basic definitions
   - 4.2 Blocks
   - 4.3 Menger's Theorem
   - 4.4 Maximum flows and minimum cuts
   
3. 5. Matchings: (slides)
   - 5.1 Basic definitions and bipartite graphs
   - 5.2 Matchings in general graphs
   
   1. Tutte's Theorem on perfect matchings
   2. Edmonds' Algorithm for finding maximum matchings in unweighted graphs
   3. A certifying extension of Edmonds' algorithm, and the Tutte-Berge formula
   - 5.3 Weighted matchings
   1. Perfect matchings in bipartite graphs, and a lower bound for their weight.
   2. Perfect matchings in general graphs, a lower bound for their weight, and Edmonds' algorithm (weighted).
4. Colorings:
   6. Edge coloring: (slides)
   - 6.1 Basic definitions and bounds
   - 6.2 Vizing's Theorem
   
   1. Vizing's Theorem
   2. An efficient algorithm for finding the edge colorings
   3. Application: time tables
   - 6.3 Approximation algorithms
   7. Vertex coloring: (slides)
   - 7.1 Basic definitions and bounds
   - 7.2 Chromatic polynomials
   - 7.3 Chordal graphs and perfect graphs
   
5. Tree decompositions and 3-connected components:
   8. Tree decompositions: (slides)
   - 8.1 Series Parallel graphs
   - 8.2 Tree decompositions: definitions and basic properties
   - 8.3 Dynamic programming over tree decompositions
   9. 3-connected components: (slides)
   - 9.1 Definition and properties of 3-connected components
   - 9.2 Decompositions into 3-connected components
   
6. 10. Planar graphs: (slides)
   - 10.1 Definition and basic properties
   
   1. Basic definitions
   2. Euler's formula
   3. Straight line embeddings and Kuratowski subdivisions
   4. Maximal planar graphs / triangulations
   - 10.2 Embeddings: equivalence, counting, and generation
   - 10.3 Layer decompositions and approximation schemes
   - 10.4 Max-Cut in planar graphs
   11. Summary. (slides).

Lecture Log

After the lectures, notes and slides can be found here.

Lectures and tutorials

Time and location of lectures:

Tuesdays 9:15-10:45 (room 1306) and Thursdays 9:15-10:45 (room 1307), Schrödinger Zentrum (Rudower Chaussee 26).

Time and location of tutorials:

Thursdays, 11:15-12:45, room 1307 of Schrödinger Zentrum (Rudower Chaussee 26).

 

 

Lecturer and tutor:

Dr. Paul Bonsma

Office hours: Tuesdays 11:00 - 12:00

Exercises

There will be weekly exercise sets. Completing these successfully (at least 40% of all points) is necessary for receiving the course credit ("Schein") and admittance to the examination.

1. The first exercise set (to be handed in on October 25). (A detailed solution for exercise 2 can be found here.)
2. The second exercise set (to be handed in on November 1).
3. The third exercise set (to be handed in on November 8). (A detailed solution for exercise 12 can be found here.)
4. The fourth exercise set (to be handed in on November 15).
5. The fifth exercise set (to be handed in on November 22).
6. The sixth exercise set (to be handed in on November 29).
7. The seventh exercise set (to be handed in on December 6).
8. The eighth exercise set (to be handed in on December 13).
9. The ninth exercise set (to be handed in on Thursday January 5).
10. The tenth exercise set (to be handed in on Tuesday January 10).
11. The eleventh exercise set (to be handed in on Tuesday January 17).
12. The twelfth exercise set (to be handed in on Tuesday January 24).
13. The thirteenth exercise set (to be handed in on Tuesday January 31).
14. The fourteenth exercise set (to be handed in on Tuesday February 7).
15. The fifteenth exercise set (to be handed in on Tuesday February 14).

Examination

In the beginning of the semester break there will be oral examinations. For admittance to these examinations at least 40% of the exercise points are necessary.

Course material

The lectures will be based on various books and journal articles. After the lectures, slides and/or lecture notes will be made available on this website.
The following books are used mainly, and recommended:

1. R. Diestel. Graph Theory, Springer, 1997, 2000, 2005, 2010 (1st-4th edition).
   Information about the book and online version.
   A book on pure graph theory, i.e. non-algorithmic.
   The following chapters are used: 1, 2, 3, 4, 5, 12.
   
   
2. A. Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer, 2003.
   Information about the book.
   A comprehensive book on polynomial time algorithms, including many graph algorithms.
   The following chapters are used: 9, 10, 15, 16, 17, 24, 26, 28, 64, 66.

In addition, selected results from the following books are used in the lectures:

1. A. V. Aho, J. E. Hopcroft, J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Publishing company, 1974.
   (Basic data structures, and details on the computation model.)
2. M. R. Garey, D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and company, 1979.
   (Contains a large collection of NP-hardness results.)
3. B. Mohar and C. Thomassen. Graphs on surfaces. John Hopkins University Press, 2001.
   (Planar graphs, embeddings, rotation systems.)
4. W. T. Tutte. Graph Theory. Addison-Wesley Publishing Company, 1984.
   (3-connected components and decompositions into 3-connected components.)
5. J. Flum, M. Grohe. Parameterized complexity theory. Springer, 2006.
   (Tree decompositions and layer decompositions of planar graphs.)
6. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
   (Dynamic programming over tree decompositions, nice tree decompositions.)

Results from the following papers are treated in the lectures:

1. J. Valdes, R. E. Tarjan, E. L. Lawler. The recognition of series parallel digraphs. In Proceedings of the eleventh annual ACM symposium on theory of computing (STOC '79), ACM, pp. 1-12, 1979.
   (Recognizing series parallel graphs in linear time and space.)
2. S. Mac Lane. A structural characterization of planar combinatorial graphs. Duke mathematical journal 3(3), 460-472, 1937.
   (3-connected components and counting embeddings.)
3. G. Di Battista, R. Tamassia. On-line planarity testing. SIAM journal on computing 25(5), 956-997, 1996.
   (Decompositions into 3-connected components / SPQR trees.)
4. M. R. Garey, D. S. Johnson, L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical computer science 1, 237-267, 1976.
   (NP-hardness results for planar versions of various graph problems.)
5. B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41(1), 153-180, 1994.
   (Layer decompositions for planar graphs, and approximation schemes.)
6. M. Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613-632, 2003.
   (Details on approximating Minimum Dominating Set using layer decompositions.)
7. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM journal on computing 4(3), 221-225, 1975.
   (Planar Max-Cut.)
8. W. Shih, S. Wu, Y. S. Kuo. Unifying maximum cut and minimum cut of a planar graph. IEEE transactions on computers 39(5), 694-697, 1990.
   (More on Planar Max-Cut.)