PhD-Course Combinatorial Optimization 1b

Venue: Utrecht University, Wiskundegebouw, room 611AB, Monday 13:00-14:45, Nov. 15, 2010 - Feb 14, 2011 (break from Dec 20, 2010 until Jan 17, 2011)

Material is taken from the lecture notes of "A course in Combinatorial Optimization" by Lex Schrijver. You can download this material from Lex' CWI website in PS or PDF-format.

The preceding course CO1a was given by Monique Laurent and covers Chapters 1 upto 5 of these notes. I will deal with chapters 6 upto 10, covering topics complexity (briefly), coloring, unimodularity, multi-commodity flows, and, if time permits, matroids. Below I briefly describe the topics treated each week, and the accompanying exercises. Those students who want the full 4 credits for this course should work out these exercises to an appropriate level. You can do this in couples of two. I hold both students totally responsible for what they or their co-author write down. The worked out exercises should be handed in or mailed after we finish the course (February 14, 2011), and before March 14, 2011. Please send your answers, either electronically, in PDF, to c.a.j.hurkens@tue.nl, or in writing, to Cor Hurkens, Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, postbus 513, 5600 MB, Eindhoven

1. Class 1, November 15, 2010.
   Contents:
   (a) problems, instances, sizes; algorithms, run time, polynomial run time. Decision problems versus Optimization problems. Course CO2a (Woeginger) deals with complexity. P: polynomially solvable problems; NP: problems with polynomially verifiable yes-instances. Example: SATISFIABILITY is in NP; Definition: a problem in NP is called DIFFICULT if it contains SATISFIABILITY as a special case. An optimization problem is called HARD if its decision version is difficult.
   Material: sections 6.1-6.10 of Lecture Notes
   Remark: the notes state that PRIMES (given a number, is it prime?) belongs to NP as well as co-NP, but it was not known whether PRIMES is in P. The case was settled in summer 2002 by three Indian scientists using he AKS algorithm. Note that this does not help us in finding the decomposition of a non-prime number. Exercise: none.
   (b) definitions of matching, edge cover, vertex cover and stable set, from chapter 3. SATISFIABILITY special case of COCLIQUE (proof). Matching and edge cover are easy, for all graphs. Vertex cover and stable set easy for bipartite graphs only. Relating problems by Gallai. Vertex coloring number of (connected) graph DIFFICULT as well.
   Material: section 3.1 and 7.1 of lecture notes.
   Exercises: 7.1, 7.2
2. Class 2, November 22, 2010.
   Contents: Vertex coloring number of (connected) graph DIFFICULT as well. Even if graph is planar. Planar graph: five-colorable (proof by Thomassen). General upper bound is Delta(G)+1 (trivial), Delta(G) in case there is vertex of lower degree, and Delta(G), in case G is not K_n or C_2n+1 (Brooks). Proof of Brooks' theorem, Berge, Hadwiger.
   sub-structures: induced subgraphs, subgraphs, minors; vertex-color-number at least clique-number, strict inequality for odd cycles and their complement;
   missed: Perfect Graph: each induced subgraph H colorable with w(H) colors; Berge Graph: no induced odd cycle (>=5) or complement;
   Berges conjecture, Hadwigers conjecture; line graph of bipartite graphs: almost also bipartite, does not contain large induced odd cycles;
   edge-color-number at least max degree, equal to max degree for bipartite graphs (with proof), edge-color-number at most max degree plus one (Vizing, with proof, details below).
   Material: sections 7.1 and 7.2 of lecture notes. Proof of Brooks (PDF). Proof of Vizing (PDF).
   Exercises: 7.6, 7.8, 7.11, 7.12 (Remark: given a ground set X, and subsets A_1,...,A_k of X, a subset T of X is called a transversal of (A_1,...,A_k), in case T ={t_1,t_2,...,t_k} with distinct t_j, such that t_j\in A_j, j=1,...,k.
3. Class 3, November 29, 2010.
   Contents: seen various min-max relations, some are TIGHT, in particular for bipartite graphs and their complements. Relevant definition: a graph is PERFECT if, for EACH INDUCED subgraph G', its vertex color number equals its largest clique size. Bipartite graph is perfect (max clique size is 1 or 2 = color number); also true for complement (with proof). Partial order, chains, anti-chains, comparability graph, Dilworth's min-max theorem. Lovasz' theorem: graph is perfect if and only if for each INDUCED subgraph alpha*omega >= number of vertices ; proof based on linear algebra.
   Material: sections 7.3 and 7.4 of lecture notes. Proof of perfectness of complement of bipartite graph (PDF).
   Exercises: 7.23, 7.26. HINT at 7.26: the nodes of the graph you have to consider are the metro lines, NOT the metro stations.
4. Class 4, December 6, 2010.
   Contents: Using Lovasz' theorem to prove min-max relations for several structures: for a bipartite graph, complement is perfect and hence edge cover number equals stable set number; the line grap of a bipartite graph is perfect, hence the edge color number of a bipartite graph equals the maximum degree.
   Further we can reprove Dilworths decompositin theorem.
   Definition of chordal graphs, simplicial vertex, intersection graph of subtrees in tree; chordal graph is perfect; chordal graph is insection graph of appropriate choice of trees; maximum number of mutually disjoint subtrees equals minimum number of tree vertices that hit all subtrees.
   Material: sections 7.4 and 7.5 of lecture notes.
   Exercises: 7.28, 7.29. HINT at 7.29: interval graph is the intersection graph of subpaths within a path (in the above replace TREE by PATH), equivalently, interval graph associates vertices with (open) intervals along real axis, and edges with interval pairs that have non-empty intersection.
5. Class 5, December 13, 2010.
   Contents: ILP = max { c'x | Ax <= b, x integer } is difficult.
   Polyhedron P = { x | Ax <= b } can be without vertices, polytope cannot. See chapter 2 for theory on Linear Programming. Polytope P is integer if each vertex is integer; generalization: a polyhedon P is integer if, for each c for which { max cx, x in P } exists, there exists an integer optimal vector. If polyhedron P = { x | Ax <= b } is given by matrix A of full column rank, again, P is integer if each vertex is integer.
   Note that max { c'x | Ax <= b, x integer } <= max { c'x | Ax <= b } = min { y'b | y'A = c', y >= 0 } <= min { y'b | y'A = c', y >= 0, y integer } . In general the inequalities are strict. For special A we have equality throughout.
   Definitions: matrix A is totally unimodular if each k by k submatrix has determinant -1,0, or +1, for k = 1,...,min{m,n}. Integer matrix A is unimodular if it is of rank m and each m by m submatrix has det = 0,-1,+1.
   Hoffman-Kruskal: A is totally unimodular if and only if, for all integer b: P_b = { x | x >= 0, Ax <= b } is integer.
   Material: chapter 2, sections 8.1, 8.2.
   Exercises: 8.7, 8.8, 8.10.
6. Class 6, January 24, 2011.
   Contents: total unimodularity of adjacency matrix of bipartite graph. Consequence: alternative proof of Koenig's theorems on matchings and edge covers. Further: weighted versions of these theorems.
   Total unimodularity of vertex-arc incidence matrix of directed graph. Reproving the max flow-min cut theorem (read for your self). Total unimodularity of interval matrix. Material planning problem for railways: a weighted circulation problem.
   Material: lecture notes, sections 8.3, 8.4.
   Exercises: 8.16, 8.18.
7. Class 7, January 31, 2011.
   Contents: recapitulation of max-flow equals min-cut theorem: s-t-cut W has capacity equal to sum of flow upper bounds on arcs leaving W minus sum of flow lower bounds on arcs entering W. Multicommodity flows are distinct s_i-t_i flows using the same network capacity. There are directed and undirected variants, fractional and integer variants, and in particular edge-disjoint, or vertex disjoint path-variants.
   Fractional variants are easy as they can be formulated as LPs; the remaining variants are almost all NP-complete, for two or more commodities.
   Necessary condition is: capacity of cut is at least demand across the cut. Often not sufficient. Sufficient to have half-integral solution for two-commodity undirected case (Hu, including proof). Material: lecture notes, sections 9.1, 9.2.
   Exercises: 9.3, 9.8.
8. Class 8, February 7, 2011.
   Contents: Extra conditions on MCFs may save the day: planarity, or in Hu's case: parity condition: for each singleton cut set, parity of capacity and demand are equal.
   Vertex disjoint paths in undirected graphs for FIXED number of source-sink-pairs is polynomially solvable; this extends to edge disjoint paths in undirected graphs. Vertex disjoint paths in directed but acyclic graphs is also easy, for FIXED number of s_i-t_i-pairs.
   Planar graphs can be embedded by 1-1 functions P,Q_e mapping nodes v to distinct points P(v), and mapping for e=(u,v) a point t \in [0,1] to Q_e(t), such that Q_e(0)=P(u), Q_e(1)=P(v), Q_e is continuous, and the images of Q_e, Q_f intersecting only at P(v) where v is an endpoint of both e and f.
   Multicommodity flows in planar graphs, with commodity end points on boundary of outer face. For the existence of vertex disjoint paths, it is required that the s_i,t_i appear along boundary in a cross-free order. A greedy algorithm decides whether or not required paths exist. A necessary condition is that each simple closed curve intersects G at least as often as it separates commodities. Robertson and Seymour prove that cross-freeness and closed-curve-cut-condition together imply the existence of the required paths.
   Material: lecture notes, sections 9.3, 9.4.
   Exercise: 9.14.
9. Class 9, February 14, 2011.
   Contents: In planar graphs, with commodity end points on boundary of outer face, we look for edge disjoint paths connecting commodities. For the existence of edge disjoint paths connecting commodities, the (regular) cut-condition (c(X)>=d(X)), does not imply the existence of paths. However, if we add the parity-condition (c(X)=d(X) modulo 2), it can be proved that paths do exist. We follow the proof by Okamura and Seymour. A tight cut is a subset X in V for which c(X)=d(X). For each tight cut X we know that each component inside G(X), or inside G(V\X), is tight as well. The combined effect of cut-condition and parity is that if c(X) < d(X), then c(X)<=d(X)-2. Replacing a commodity (s,t), by two commodities (s,v) and (v,t) can yield a violated cut S only if it separates v from s and t and originally S was tight.
   Material: lecture notes, sections 9.4, 9.5.
   Exercises: None.