Shortest Paths and T-Joins in Graph Theory

4. Conservative weightings Undirected shortest paths T-joins

Paths in Graphs Directed, nonnegative weights (Dijkstra) -1 weights NP-hard (HAM) Conservative (no circuit of neg total weight): P Undirected shortest paths with nonnegative weights ? With -1 weights ? With a conservative weighting ? Exercise : Does the triangle inequality hold in the undirected case ? Are subpaths of shortest paths shortest ? Can we solve undirected shortest path problems in the same way as directed ones ? Or reduce one to the other ?

a Conservativeness Def: (G,w) where G is a graph, w: E(G) Z is conservative, if for every circuit C of G : w(C) 0 . (x,y) : = w(x,y) : = min {w(P) : P path } = ? (a,b) = (a,c)= -1 ; (b,c)= -2 ; (a,b) + (b,c) < (a,c) a c b -1 -1 A shortest (a,c)-path is not shortest between a and b. Exercise 3.4 Recursively with `Matrix Multiplication ? Bellman-Ford ? Floyd-Warshall ? negative cycle NO !

T-joins TG-joins, where TG :={v: d(v) is odd} F E(G) is a T-join, if Euler s theorem : G= (V,E), E : streets One can go through all the streets Exactly once G conn., degree even T = vertices of odd degree of F. Easy facts about T-joins : G connected, |T| even T-join ; min weight Eulerian replication = duplication of a min weight TG-join Exercise 3.1 G=(V,E), w: E IR, F is a minimum weight T-join (G, w[F]) is conservative, where w[F](e):= 1 ?? ? ? Exercise 3.2 1 ?? ? ? Is it true : (x,y) : = w(x,y) : = min {w(P) : P {x,y}-join} ?

A Quick Proof of Seymours theorem Theorem: G bipartite, w:E(G) {-1,1} , (G,w) conservative E- can be covered by disj cuts meeting it in exactly one edge each. Exercise 4.5 x0 V(G) Take b x0 such that w(x0,b)=minv V(G) w(x0,v) Proof : S. : `Quick Proof , & x0 x0 x0 Claim 1 :| (b) E- | =1 C Exercise 4.3 b Claim 2 : Swapping on a circuit C, w(C)=0 : x0 w[C] is conservative b Claim 3 : Contracting (b) deleting loops, cons. is kept ! Exercise 4.4

T-cuts Def : (W) E(G) (W V) is a T-cut, if |W T| is odd Proposition : F T-join, (W) T-cut | F (W) | 1 (G,T) (G,T) min { |F| : F E, F is a T-join } max{ |C|: C disjoint T-cuts } := := (G,T)=2 (G,T)=1 T:=V Easy : (G,T) (G,T) Exercise 5.1 Theorem(Seymour 81) If G is bipartite, (G,T) = (G,T)

Nonbipartite minmax Exercise 5.3 2(G,T) := max{ |C|: C 2-packing of T-cuts }, where a 2-packing is a family covering every element twice Easy : (G,T) 2 (G,T) /2 Proof : Let F be a T-join, and C a 2-packing of T-cuts. Then 2 | F | ? ?? C|F C| |C | 2 (G,T) = = 2 (G,T) On two minmax theorems in graph Theorem (Lov sz 76) If G is arbitrary : (G,T) = 2 (G,T) /2 Theorem (Edmonds-Johnson 73) G=(V,E) (G,T) = * (G,T)

Polynomial algorithm for the postman Input : G=(V,E), w: E IR Task : minimize the weight of a T-join Proposition (Edmonds) : If the weights are nonnegative easy reduction: min weight matching of the complete graph on T where the weights are the w-shortest paths in G between the vertices of T. Can we find a negative circuit and shortest paths in undirected graphs ? Can we reduce the augmenting paths for matchings to this ?

6. Linear Programming (LP)

LP for bipartite matchings MATCHING POLYTOPE for G=(V,E) bipartite x IRE : x ( (v)) 1 , v V x 0 Dual for the all 1 objective function: VERTEX COVER for G=(V,E) bipartite x IRV : xi + xj 1 , ij E x 0 Proof : TDI , TU+Cramer, or comb. no odd circuit)

6.1 Fractional chromatic index M : set of all matchings fractional chromatic index := * = Min ? ?? MyM , yM 0 ? ?? M contains eyM 1 (or w(e) where w is non-neg edge-weights) * = (G,w) = Min : w / matching polytope : in addition integer and w = integer comb of M What is * for bipartite matchings ?

Minmax and computation of * Fractional Chromatic Index for bipartite graphs ? At least for all graphs so = for bip;1/ on all edges polytope For general graphs ? Min : w / matching polytope x IRE : x ( (v)) 1, x 0 x (E(U)) |U| 1 2 , 2w(? ? ) |U| 1 Edmonds (1965) U V , |U| odd , Polynomial algorithm ! Compare with average degree 2w(? ? ) How does it compare if all weights are 1 (simple graphs) ? ! |U|

Nonbipartite matching polytope The Perfect Matching Polytope: K nig (1916), Jacobi (1890) Egerv ry (1931), Birkhoff (1946), von Neuman (1952): easier to prove If G is bipartite : conv ( M : M p.m. ) = {x IRE : x ( (v))=1, x 0 } If G is arbitrary : Edmonds (1965), add : if U V , |U| is odd x ( (U)) 1 The linear inequalities of the Matching Polytope of G=(V,E): x IRE : x ( (v)) 1, x 0 x (E(U)) |U| 1 2 Edmonds (1965) U V , |U| odd

Conjectures about additive gap 0 or 1 P(G) matching polytope, k integer, w k M (G) integer. . Conjecture (Lov sz ) : G without Petersen minor = * i.e. w = M1 + + Mk Conjectures (Schrijver) : t-perfect graphs Conjecture (Goldberg, Seymour ) : MID = ID +1 x matching(G) x is +1 colorable; tight: Petersen Conjecture (Aharoni): matroid indep set are MID Conjecture (Scheithauer and Terno): cutting stock (bin packing patterns) are MID.

6.2 How are LP, polyhedra useful for insight ? Lower bound because relaxation Can be part of the solution algorithm Example of another use : A generalization of Petersen s theorem

Petersens theorem (1891) A graph is cubic if all of its degrees are 3. Theorem: G is a cubic graph G has no bridge G has a p.m.

Weighted generalization Exercise : Let G=(V,E) be cubic, w: E IR on the edges. Then a. If G is bipartite, or b. If G is arbitrary bridgeless There exists a p.m. of weight 1/3 w(E) 12 15 6 9 10 + 9 + 11 + 2x15 = 60 1/3 w(E) (w (E) = 179 ) 8 15 11 10 7 6 5 Bridgeless, but cannot be partitioned to 3 p.m.

Through the polyhedral lens If G=(V,E) cubic, bipartite The constant 1/3 function on the edges is in the convex hull of matchings. If G=(V,E) cubic, bridgeless The constant 1/3 function on the edges is in the convex hull of matchings. If G is cubic, bridgeless (or bipartite), matching valued random variable M so that E(M) = constant 1/3 on E . Theorem: G=(V,E) cubic, bridgeless (or bipartite), w: E IR. matching M,w M ?(?)/3

6.3 The T-join polyhedron Method: the inverse of the duality theorem Theorem Edmonds,Johnson (1973) : Q+(G,T) := conv (T-joins) + IR+n = {x IR+E x( (W)) 1, (W) is a T-cut, i.e. |W T| is odd} : Clear ! Proof : For = show c IRS min cTx for x on the left = min cTx for x on the right This suffices , since if not =, then and the hyperplane cTx=b separating some x on the right from all on the left (=> c 0 maybe changing the sign), shows that the min of cTx is smaller on the right . But min of cTx on the right is equal, by the duality theorem to the max of its dual so the latter is smaller then the min of cTx on the left, contradicting Edmonds and Johnson s minimax theorem (Corollary of Seymour s theorem):

Proving the T-join polyhedron Thm Metatheorem : weighted minmax theorem ( -approximation for all weights polyhedron - polyhedron containment ) . Q.E.D. . Edmonds-Johnson : (G,T, c)= *(G,T,c):= fractional opt . . Lov sz (76): If G arbitrary, (G,T) = 2(G,T) /2 Seymour (81): If G is bipartite, (G,T) = (G,T)

End of Part A: MATCHINGS To come : TSP + a bit of submodularity, matroids Exercises for the Courses 3-4 : series 6