SCHEDULE

Recommended arrival time at Berlin: April 1, Sunday.

First lecture: April 2, Monday, 9:00 a.m.
Last day: April 12 (Thursday).

The only free day is April 8 (Sunday), that is, the course consists of ten working days. Each working day there are three 60-minute lectures in the morning: 9:00-10:00, 10:15-11:15, 11:30-12:30 and a 90-minute exercise in the afternoon: 14:30-16:00. (This timing however is changeable for request). The remaining part of the day is free (for independent working).

The major goal is not only to learn some nice new theorems and algorithms but to understand how these results were invented and how you could figure out their proof. Special emphasis will be given to exploring links between apparently different areas. (For example, however unexpected it is, the following two problems turn out to have one source in common: 1) add a minimum number of edges to a digraph to make it k-connected, 2) find a minimum number of rectangles to cover a vertically convex rectilinear polygon). We also want to demonstrate, by exhibiting several exciting concrete special cases, why abstract frameworks, like (poly)matroids submodular flows and others, are worth for studying. Here is a list of topics we are going to touch. Emphasis may vary depending on the knowledge and interest of the audience.

In order to have some flavour of the course, here is a LIST OF PROBLEMS we will touch, probably not all and neither exclusively.

1. BASIC TECHNIQUES AND RESULTS
   (We exhibit some basic techniques acting in their simplest form, and prove some classical theorems of combinatorial optimization.)
   1. Reduction along critical sets: proof of theorems of Hall, Menger, Dilworth, and Tutte's matching.
   2. Elements of the submodular technique. Proof of Hall, Hoffman's circulation, submodular flow feasibilty, matroid partition theorem.
   3. Elementary construction. Menger-versions from directed edge-Menger. Defect-version of Hall, König from Hall, Dilworth from König, Menger from König, Berge-Tutte formula from Tutte, MFMC from Hoffman circulation and vice versa. From submodular flow feasibility to discrete separation.
   4. Splitting off: Menger, Lovász+Cherkasskij on A-paths.
   5. The uncrossing technique: Seymour's matroid list-colouring. A minimal k-edge-connected graph has at most k(n-1) edges. Dilworth-truncation of intersecting submodular functions.
   6. Linear programming. Farkas, Duality, optimality criteria, and their special form for totally unimodular (TU) constraint matrix. Hoffman=Farkas+TU. König=LP-duality +TU. Degree-constrained subgraphs. Solving network-matrix constrained linear programs by network flows. Uniform colourings of bipartite graphs and interval systems. Conservative weightings of digraphs.
   7. Constructive characterizations: Ear-decompositions. Consructing of all 2-edge-connected, 2-connected graphs, strongly connected digraphs, elementary bipartite graphs, factor-critical graphs.
   8. Some NP-complete problems: Hamiltonian path, Two edge-disjoint paths in digraphs, min. cost strongly-connected augmentation of digraphs, etc.
2. BASIC ALGORITHMIC APPROACHES
   
   1. Searches: DFS, BFS, SFS, Nagamochi and Ibaraki mincut, small certificates for high connectivity.
   2. Greedy algorithm: max weight basis in a matroid, two-phase greedy algorithms: shortest paths for non-negative weights, longest chain in a poset, packing subtrees in a tree, minimum cost arborescences.
   3. Dynamic programming. Shortest paths for conservative weights, Steiner trees in planar graphs. Disjoint paths in acyclic digraphs.
   4. Alternatig path method. König, indegree-constrained orientation of graphs, the linking property, MFMC, Preflow algorithm.
3. (EASY) ORIENTATIONS
   

   Strongly connected (=strong) orientation of mixed graphs, degree-constrained strong orientations. k-root-connected orientations.

4. PACKING AND COVERING WITH TREES AND ARBORESCENCES}
   

   Edmonds' disjoint arborescences, Tutte's disjoint spanning trees, covering a digraph by k arborescences (Vidyasankar) and by k branchings, covering a graph by k trees (Nash-Williams).

5. THE UNCROSSING TECHNIQUE}
   

   Mader: Minimally k-edge-connected digraphs have a node of on-degree and out-degree k. The Lucchesi-Younger theorem (making a digraph strong by contracting a minimum number of edges), and an application: edge-disjoint paths in acyclic planar digraphs. The minimum weight of a spanning arborescence (Fulkerson). Increasing the rooted edge- and node-connectivity by one of a digraph. Increasing the edge-connectivity and the node-connectivity of a digraph by one. Györi's theorem on covering a rectilinear polygon by rectangles.

6. DIRECTED SPLITTING-OFF
   

   Mader's directed splitting-off theorem. Constructing all k-edge-connected and all rooted k-edge-connected digraphs. Corollary: Edmonds disjoint arborescences. Construction of all graphs with k disjoint spanning trees. Making a digraph k-ec by adding a minimum number of new edges.

7. UNDIRECTED SPLITTING-OFF
   

   Lovász' splitting off. Constructing all k-ec graphs. Increasing the edge-connectivity of a graph (Watanabe-Nakamura). Nash-Williams' orientation theorem. Mader's undirected splitting. Increasing the local edge-connectivity of a graph.

8. T-JOINS AND T-CUTS
   

   The chinese postman problem, Sebö's lemma, Seymour's theorem, conservative weightings in undirected graphs.

9. DISJOINT PATHS PROBLEMS
   

   Theorems of Okamura-Seymour, Hu, Seymour, Okamura, Lomonosov.

10. MATROID AND POLYMATROID OPTIMIZATION

    Greedy algorithm, the partition and intersection algorithms of Edmonds, weighted matroid intersection algorithm. Packing and covering problems, theorems of Rado, Edmonds and Nash-Williams. Applications to graph and hypergraph connectivity problems.

11. TOTAL DUAL INTEGRALITY

    Submodular flows (Edmonds and Giles), Generalized polymatroids and the linking property. Fujishige's theorem on the basis polyhedron. General orientation results. How to orient a mixed graph to make it k-edge-connected. Combining connectivity orientation and augmentation results.

    XII. GENERAL FRAMEWORKS FOR SUB- OR SUPERMODULAR FUNCTIONS
    

    Applications: General connectivity augmentation in digraphs. Finding minimum cost rooted k-connected subgraphs in a digraph. Orientation again: when does a mixed graph have a k-edge-connected orientation.

12. ALGORITHMS
    

    Two-phase greedy algorithms. Queyranne: minimizing symmetric submodular functions. Algorithm for Györi's theorem. Algorithm for theorems of Greene and of Greene-Kleitman to find the largest union of k chains or k antichains of a poset.