Combinatorial optimization, polyhedra and efficiency. Vol.A,B,C

COMBINATORIAL OPTIMIZATION......Page 1
Title Page......Page 4
Copyright Page......Page 5
Preface......Page 6
Volume A......Page 10
Volume B......Page 23
Volume C......Page 33
1.1 Introduction......Page 39
1.2 Matchings......Page 40
1.3 But what about nonbipartite graphs?......Page 42
1.4 Hamiltonian circuits and the traveling salesman problem......Page 43
1.5a Historical sketch on polyhedral combinatorics......Page 44
1.5b Further notes......Page 46
2.1 Sets......Page 47
2.4 Vectors, matrices, and functions......Page 49
2.6 Fekete's lemma......Page 52
3.1 Undirected graphs......Page 54
3.2 Directed graphs......Page 66
3.3 Hypergraphs......Page 74
3.3a Background references on graph theory......Page 75
4.1 Introduction......Page 76
4.3 Polynomial-time solvability......Page 77
4.5 NP......Page 78
4.7 Optimization problems......Page 80
4.8 NP-complete problems......Page 81
4.10 NP-completeness of the satisfiability problem......Page 82
4.11 NP-completeness of some other problems......Page 84
4.12 Strongly polynomial-time......Page 85
4.13 Lists and pointers......Page 86
4.14b Efficiency and complexity historically......Page 87
5.1 Convexity and halfspaces......Page 97
5.3 Polyhedra and polytopes......Page 98
5.5 Linear programming......Page 99
5.6 Faces, facets, and vertices......Page 101
5.8 Blocking polyhedra......Page 103
5.10 Methods for linear programming......Page 105
5.11 The ellipsoid method......Page 106
5.12 Polyhedra and NP and co-NP......Page 109
5.13 Primal-dual methods......Page 110
5.14 Integer linear programming......Page 111
5.15 Integer polyhedra......Page 112
5.16 Totally unimodular matrices......Page 113
5.17 Total dual integrality......Page 114
5.18 Hilbert bases and minimal TDI systems......Page 119
5.19 The integer rounding and decomposition properties......Page 120
5.21 The integer hull and cutting planes......Page 121
5.21a Background literature......Page 122
Part I: Paths and Flows......Page 123
6.1 Shortest paths with unit lengths......Page 125
6.2 Shortest paths with unit lengths algorithmically: breadth-first search......Page 126
6.3 Depth-first search......Page 127
6.5a All-pairs shortest paths in undirected graphs......Page 129
6.5c Ear-decomposition of strongly connected digraphs......Page 131
6.5e Further notes......Page 132
7.1 Shortest paths with nonnegative lengths......Page 134
7.2 Dijkstra's method......Page 135
7.3 Speeding up Dijkstra's algorithm with k-heaps......Page 136
7.4 Speeding up Dijkstra's algorithm with Fibonacci heaps......Page 137
7.5a Weakly polynomial-time algorithms......Page 139
7.5b Complexity survey for shortest paths with nonnegative lengths......Page 141
7.5c Further notes......Page 143
8.2 Potentials......Page 145
8.3 The Bellman–Ford method......Page 147
8.4 All-pairs shortest paths......Page 148
8.5 Finding a minimum-mean length directed circuit......Page 149
8.6a Complexity survey for shortest path without negative-length circuits......Page 150
8.6b NP-completeness of the shortest path problem......Page 152
8.6c Nonpolynomiality of Ford's method......Page 153
8.6d Shortest and longest paths in acyclic graphs......Page 154
8.6e Bottleneck shortest path......Page 155
8.6f Further notes......Page 156
8.6g Historical notes on shortest paths......Page 157
9.1 Menger's theorem......Page 169
9.1a Other proofs of Menger's theorem......Page 171
9.2 Path packing algorithmically......Page 172
9.3 Speeding up by blocking path packings......Page 173
9.4 A sometimes better bound......Page 174
9.5 Complexity of the vertex-disjoint case......Page 175
9.6a Complexity survey for the disjoint s–t paths problem......Page 176
9.6c Exchange properties of disjoint paths......Page 178
9.6d Further notes......Page 179
9.6e Historical notes on Menger's theorem......Page 180
10.1 Flows: concepts......Page 186
10.2 The max-flow min-cut theorem......Page 188
10.4 Finding a maximum flow......Page 189
10.4a Nontermination for irrational capacities......Page 190
10.5 A strongly polynomial bound on the number of iterations......Page 191
10.6 Dinits' O(n²m) algorithm......Page 192
10.6a Karzanov's O(n³) algorithm......Page 193
10.7 Goldberg's push-relabel method......Page 194
10.8a A weakly polynomial bound......Page 197
10.8b Complexity survey for the maximum flow problem......Page 198
10.8d Further notes......Page 200
10.8e Historical notes on maximum flow......Page 202
11.1 A useful fact on arc functions......Page 208
11.2 Circulations......Page 209
11.3 Flows with upper and lower bounds......Page 210
11.4 b-transshipments......Page 211
11.5 Upper and lower bounds on excess f......Page 212
11.6 Finding circulations and transshipments algorithmically......Page 213
11.6a Further notes......Page 214
12.1 Minimum-cost flows and circulations......Page 215
12.2 Minimum-cost circulations and the residual graph D f......Page 216
12.3 Strongly polynomial-time algorithm......Page 217
12.4 Related problems......Page 220
12.4a A dual approach......Page 221
12.4b A strongly polynomial-time algorithm using capacity-scaling......Page 224
12.5a Complexity survey for minimum-cost circulation......Page 228
12.5b Min-max relations for minimum-cost flows and circulations......Page 229
12.5c Dynamic flows......Page 230
12.5d Further notes......Page 233
13.1 Path polyhedra......Page 236
13.1a Vertices, adjacency, and facets......Page 240
13.1b The s–t connector polytope......Page 241
13.2 Total unimodularity......Page 242
13.2a Consequences for flows......Page 243
13.2c Consequences for transshipments......Page 245
13.2d Unions of disjoint paths and cuts......Page 248
13.3 Network matrices......Page 251
13.4 Cross-free and laminar families......Page 252
14.1 Partially ordered sets......Page 255
14.2 Dilworth's decomposition theorem......Page 256
14.3 Path coverings......Page 257
14.4 The weighted case......Page 258
14.5 The chain and antichain polytopes......Page 259
14.5a Path coverings algorithmically......Page 260
14.6 Unions of directed cuts and antichains......Page 262
14.6a Common saturating collections of chains......Page 264
14.7 Unions of directed paths and chains......Page 265
14.7a Common saturating collections of antichains......Page 267
14.7b Conjugacy of partitions......Page 268
14.8a The Gallai–Milgram theorem......Page 270
14.8b Partially ordered sets and distributive lattices......Page 271
14.8c Maximal chains......Page 273
14.8d Further notes......Page 274
15.1 Vertex-, edge-, and arc-connectivity......Page 275
15.2 Vertex-connectivity algorithmically......Page 277
15.2a Complexity survey for vertex-connectivity......Page 279
15.2b Finding the 2-connected components......Page 280
15.3 Arc- and edge-connectivity algorithmically......Page 281
15.3a Complexity survey for arc- and edge-connectivity......Page 284
15.3b Finding the 2-edge-connected components......Page 285
15.4 Gomory–Hu trees......Page 286
15.4a Minimum-requirement spanning tree......Page 289
15.5a Ear-decomposition of undirected graphs......Page 290
15.5b Further notes......Page 291
Part II: Bipartite Matching and Covering......Page 295
16.1 M-augmenting paths......Page 297
16.2 Frobenius' and König's theorems......Page 298
16.2b Linear-algebraic proof of Frobenius' theorem......Page 300
16.3 Maximum-size bipartite matching algorithm......Page 301
16.4 An O(n^1/2 m) algorithm......Page 302
16.6 Matchings covering given vertices......Page 303
16.7b Finding perfect matchings in regular bipartite graphs......Page 305
16.7c The equivalence of Menger's theorem and König's theorem......Page 313
16.7e Equivalent formulations in terms of partitions......Page 314
16.7g Further notes......Page 315
16.7h Historical notes on bipartite matching......Page 316
17.1 Weighted bipartite matching......Page 323
17.2 The Hungarian method......Page 324
17.3 Perfect matching and assignment problems......Page 326
17.4 Finding a minimum-size w-vertex cover......Page 327
17.5b Further notes......Page 328
17.5c Historical notes on weighted bipartite matching and optimum assignment......Page 330
18.1 The matching and the perfect matching polytope......Page 339
18.2 Totally unimodular matrices from bipartite graphs......Page 341
18.3 Consequences of total unimodularity......Page 342
18.5b Dual, primal-dual, primal?......Page 343
18.5c Adjacency and diameter of the matching polytope......Page 345
18.5d The perfect matching space of a bipartite graph......Page 346
18.5e Up and down hull of the perfect matching polytope......Page 347
18.5f Matchings of given size......Page 348
18.5g Stable matchings......Page 349
18.5h Further notes......Page 352
19.1 Matchings, edge covers, and Gallai's theorem......Page 353
19.3 Finding a minimum-weight edge cover......Page 355
19.5 The edge cover and stable set polytope......Page 356
19.5a Some historical notes on bipartite edge covers......Page 357
20.1 Edge-colourings of bipartite graphs......Page 359
20.2 The capacitated case......Page 360
20.3 Edge-colouring polyhedrally......Page 361
20.4 Packing edge covers......Page 362
20.5 Balanced colours......Page 363
20.6 Packing perfect matchings......Page 364
20.6a Polyhedral interpretation......Page 365
20.6b Extensions......Page 366
20.7 Covering by perfect matchings......Page 367
20.7a Polyhedral interpretation......Page 368
20.8 The perfect matching lattice of a bipartite graph......Page 369
20.9a Some further edge-colouring algorithms......Page 371
20.9b Complexity survey for bipartite edge-colouring......Page 372
20.9c List-edge-colouring......Page 373
20.9d Further notes......Page 374
21.1 b-matchings and w-vertex covers......Page 375
21.2 The b-matching polytope and the w-vertex cover polyhedron......Page 376
21.3 Simple b-matchings and b-factors......Page 377
21.4 Capacitated b-matchings......Page 379
21.5 Bipartite b-matching and w-vertex cover algorithmically......Page 380
21.6 Transportation......Page 381
21.6a Reduction of transshipment to transportation......Page 383
21.6b The transportation polytope......Page 384
21.7 b-edge covers and w-stable sets......Page 385
21.8 The b-edge cover and the w-stable set polyhedron......Page 386
21.9 Simple b-edge covers......Page 387
21.10 Capacitated b-edge covers......Page 388
21.11 Relations between b-matchings and b-edge covers......Page 389
21.12 Upper and lower bounds......Page 391
21.13a Complexity survey on weighted bipartite b-matching and transportation......Page 393
21.13c Existence of matrices......Page 397
21.13d Further notes......Page 399
21.13e Historical notes on the transportation and transshipment problems......Page 400
22.1 Transversals......Page 416
22.1a Alternative proofs of Hall's marriage theorem......Page 417
22.2 Partial transversals......Page 418
22.4 Min-max relations for weighted transversals......Page 420
22.5 The transversal polytope......Page 421
22.6 Packing and covering of transversals......Page 423
22.7a The capacitated case......Page 425
22.7c Further notes......Page 427
22.7d Historical notes on transversals......Page 428
23.1 Common transversals......Page 431
23.2 Weighted common transversals......Page 433
23.3 Weighted common partial transversals......Page 435
23.4 The common partial transversal polytope......Page 437
23.5 The common transversal polytope......Page 439
23.6 Packing and covering of common transversals......Page 440
23.7b Exchange properties......Page 445
23.7c Common transversals of three families......Page 446
23.7d Further notes......Page 447
Part III: Nonbipartite Matching and Covering......Page 449
24.1 Tutte's 1-factor theorem and the Tutte–Berge formula......Page 451
24.2 Cardinality matching algorithm......Page 453
24.2a An O(n³) algorithm......Page 456
24.3 Matchings covering given vertices......Page 459
24.4a Complexity survey for cardinality nonbipartite matching......Page 460
24.4b The Edmonds–Gallai decomposition of a graph......Page 461
24.4d Ear-decomposition of factor-critical graphs......Page 463
24.4e Ear-decomposition of matching-covered graphs......Page 464
24.4f Barriers in matching-covered graphs......Page 465
24.4g Two-processor scheduling......Page 466
24.4h The Tutte matrix and an algebraic matching algorithm......Page 467
24.4i Further notes......Page 468
24.4j Historical notes on nonbipartite matching......Page 469
25.1 The perfect matching polytope......Page 476
25.2 The matching polytope......Page 477
25.3 Total dual integrality: the Cunningham–Marsh formula......Page 478
25.3a Direct proof of the Cunningham–Marsh formula......Page 480
25.4 On the total dual integrality of the perfect matching constraints......Page 481
25.5a Adjacency and diameter of the matching polytope......Page 482
25.5b Facets of the matching polytope......Page 484
25.5c Polynomial-time solvability with the ellipsoid method......Page 486
25.5d The matchable set polytope......Page 488
25.5e Further notes......Page 490
26.1 Introduction and preliminaries......Page 491
26.2 Weighted matching algorithm......Page 492
26.2a An O(n³) algorithm......Page 494
26.3a Complexity survey for weighted nonbipartite matching......Page 496
26.3c Further notes......Page 497
27.1 Minimum-size edge cover......Page 499
27.2 The edge cover polytope and total dual integrality......Page 500
27.3b Historical notes on edge covers......Page 502
28.1 Vizing's theorem for simple graphs......Page 503
28.2 Vizing's theorem for general graphs......Page 505
28.3 NP-completeness of edge-colouring......Page 506
28.4 Nowhere-zero flflows and edge-colouring......Page 508
28.5 Fractional edge-colouring......Page 512
28.6 Conjectures......Page 513
28.7 Edge-colouring polyhedrally......Page 515
28.8 Packing edge covers......Page 516
28.9b Further notes......Page 518
28.9c Historical notes on edge-colouring......Page 520
29.1 T-joins......Page 523
29.3 The Chinese postman problem......Page 525
29.4 T-joins and T-cuts......Page 526
29.5 The up hull of the T-join polytope......Page 528
29.6 The T-join polytope......Page 529
29.7 Sums of circuits......Page 531
29.8 Integer sums of circuits......Page 532
29.9 The T-cut polytope......Page 536
29.10 Finding a minimum-capacity T-cut......Page 537
29.11a Minimum-mean length circuit......Page 538
29.11b Packing T-cuts......Page 539
29.11c Packing T-joins......Page 545
29.11d Maximum joins......Page 548
29.11e Odd paths......Page 553
29.11f Further notes......Page 555
29.11g On the history of the Chinese postman problem......Page 557
30.1 2-matchings and 2-vertex covers......Page 558
30.2 Fractional matchings and vertex covers......Page 559
30.4 The 2-matching polytope......Page 560
30.5 The weighted 2-matching problem......Page 561
30.5a Maximum-size 2-matchings and maximum-size matchings......Page 562
30.6 Simple 2-matchings and 2-factors......Page 564
30.7 The simple 2-matching polytope and the 2-factor polytope......Page 566
30.9 2-edge covers and 2-stable sets......Page 569
30.10 Fractional edge covers and stable sets......Page 570
30.12 The 2-edge cover polyhedron......Page 571
30.13 Total dual integrality of the 2-edge cover constraints......Page 572
30.14 Simple 2-edge covers......Page 573
30.15 Graphs with ν(G) = τ(G) and α(G) = ρ(G)......Page 574
30.16 Excluding triangles......Page 577
30.16b Packing edges and factor-critical subgraphs......Page 582
30.16c 2-factors without short circuits......Page 583
31.1 b-matchings......Page 584
31.2 The b-matching polytope......Page 585
31.3 Total dual integrality......Page 588
31.4 The weighted b-matching problem......Page 592
31.5 If b is even......Page 594
31.6 If b is constant......Page 596
31.7b Facets and minimal systems for the b-matching polytope......Page 597
31.7c Regularizable graphs......Page 598
31.7d Further notes......Page 599
32.1 Capacitated b-matchings......Page 600
32.2 The capacitated b-matching polytope......Page 602
32.3 Total dual integrality......Page 604
32.4a Further notes......Page 605
33.1 Simple b-matchings and b-factors......Page 607
33.3 Total dual integrality......Page 608
33.4 The weighted simple b-matching and b-factor problem......Page 609
33.5 If b is constant......Page 610
33.6b Degree-sequences......Page 611
33.6c Further notes......Page 612
34.1 b-edge covers......Page 613
34.3 Total dual integrality......Page 614
34.4 The weighted b-edge cover problem......Page 615
34.6 If b is constant......Page 616
34.7 Capacitated b-edge covers......Page 617
34.8 Simple b-edge covers......Page 619
34.8a Simple b-edge covers and b-matchings......Page 620
34.8b Capacitated b-edge covers and b-matchings......Page 621
35.1 Upper and lower bounds......Page 622
35.2 Convex hull......Page 624
35.3 Total dual integrality......Page 627
35.4a Further results on subgraphs with prescribed degrees......Page 629
35.4b Odd walks......Page 631
36.1 Bidirected graphs......Page 632
36.2 Convex hull......Page 635
36.3 Total dual integrality......Page 636
36.4 Including parity conditions......Page 638
36.5 Convex hull......Page 642
36.6 Total dual integrality......Page 643
36.7a The Chvátal rank......Page 645
36.7b Further notes......Page 646
37.1 The dimension of the perfect matching polytope......Page 647
37.2 The perfect matching space......Page 649
37.3 The brick decomposition......Page 650
37.4 The brick decomposition of a bipartite graph......Page 651
37.6 Bricks......Page 652
37.7 Matching-covered graphs without nontrivial tight cuts......Page 655
38.1 The perfect matching lattice......Page 657
38.2 The perfect matching lattice of the Petersen graph......Page 658
38.3 A further fact on the Petersen graph......Page 659
38.4 Various useful observations......Page 660
38.5 Simple barriers......Page 662
38.6 The perfect matching lattice of a brick......Page 668
38.7 Synthesis and further consequences of the previous results......Page 681
38.8 What further might (not) be true......Page 682
38.9a The perfect 2-matching space and lattice......Page 684
38.9b Further notes......Page 685
Part IV: Matroids and Submodular Functions......Page 687
39.1 Matroids......Page 689
39.2 The dual matroid......Page 690
39.3 Deletion, contraction, and truncation......Page 691
39.4 Examples of matroids......Page 692
39.4a Relations between transversal matroids and gammoids......Page 697
39.6 Characterizing matroids by circuits......Page 700
39.6a A characterization of Lehman......Page 701
39.7 Characterizing matroids by rank functions......Page 702
39.8a Characterizing matroids by span functions......Page 704
39.8b Characterizing matroids by flats......Page 705
39.8c Characterizing matroids in terms of lattices......Page 706
39.9 Further exchange properties......Page 707
39.10a Further notes......Page 709
39.10b Historical notes on matroids......Page 710
40.1 The greedy algorithm......Page 726
40.2 The independent set polytope......Page 728
40.3 The most violated inequality......Page 731
40.3a Facets and adjacency on the independent set polytope......Page 736
40.3b Further notes......Page 737
41.1 Matroid intersection theorem......Page 738
41.1a Applications of the matroid intersection theorem......Page 740
41.1b Woodall's proof of the matroid intersection theorem......Page 742
41.2 Cardinality matroid intersection algorithm......Page 743
41.3 Weighted matroid intersection algorithm......Page 745
41.3a Speeding up the weighted matroid intersection algorithm......Page 748
41.4 Intersection of the independent set polytopes......Page 750
41.4a Facets of the common independent set polytope......Page 755
41.4b Up and down hull of the common base polytope......Page 757
41.5a Menger's theorem for matroids......Page 758
41.5b Exchange properties......Page 759
41.5c Jump systems......Page 760
41.5d Further notes......Page 761
42.1 Matroid union theorem......Page 763
42.1a Applications of the matroid union theorem......Page 765
42.1b Horn's proof......Page 767
42.2 Polyhedral applications......Page 768
42.3 Matroid union algorithm......Page 769
42.4 The capacitated case: fractional packing and covering of bases......Page 770
42.5 The capacitated case: integer packing and covering of bases......Page 772
42.6a Induction of matroids......Page 774
42.6b List-colouring......Page 775
42.6c Strongly base orderable matroids......Page 776
42.6d Blocking and antiblocking polyhedra......Page 779
42.6f Historical notes on matroid union......Page 781
43.1 Infinite matroids......Page 783
43.2 Matroid matchings......Page 784
43.4 A special class of matroids......Page 785
43.5 A min-max formula for maximum-size matroid matching......Page 789
43.6 Applications of the matroid matching theorem......Page 791
43.7 A Gallai theorem for matroid matching and covering......Page 794
43.8 Linear matroid matching algorithm......Page 795
43.9 Matroid matching is not polynomial-time solvable in general......Page 800
43.10a Optimal path-matching......Page 801
43.10b Further notes......Page 802
44.1 Submodular functions and polymatroids......Page 804
44.1a Examples......Page 806
44.2 Optimization over polymatroids by the greedy method......Page 809
44.4 f is determined by EP f......Page 811
44.5 Supermodular functions and contrapolymatroids......Page 812
44.6a Submodular functions and matroids......Page 813
44.6c The structure of polymatroids......Page 814
44.6d Characterization of polymatroids......Page 817
44.6e Operations on submodular functions and polymatroids......Page 819
44.6g Induction of polymatroids......Page 820
44.6h Lovász's generalization of König's matching theorem......Page 821
44.6i Further notes......Page 822
45.1 Submodular function minimization......Page 824
45.3 A subroutine......Page 825
45.4 Minimizing a submodular function......Page 827
45.5 Running time of the algorithm......Page 828
45.6 Minimizing a symmetric submodular function......Page 830
45.7 Minimizing a submodular function over the odd sets......Page 831
46.1 Box-total dual integrality of polymatroid intersection......Page 833
46.2 Consequences......Page 834
46.3 Contrapolymatroid intersection......Page 835
46.4 Intersecting a polymatroid and a contrapolymatroid......Page 836
46.5 Frank's discrete sandwich theorem......Page 837
46.6 Integer decomposition......Page 838
46.7a Up and down hull of the common base vectors......Page 839
46.7b Further notes......Page 842
47.1 A maximum-size common vector in two polymatroids......Page 843
47.2 Maximizing a coordinate of a common base vector......Page 845
47.3 Weighted polymatroid intersection in polynomial time......Page 847
47.4 Weighted polymatroid intersection in strongly polynomial time......Page 849
47.6 Intersecting a polymatroid and a contrapolymatroid......Page 856
47.6a Further notes......Page 857
48.1 If f(∅) < 0......Page 858
48.2 Dilworth truncation......Page 859
48.2a Applications and interpretations......Page 861
48.3 Intersection......Page 863
49.1 Submodular functions on a lattice family......Page 864
49.2 Intersection......Page 866
49.3 Complexity......Page 867
49.4 Submodular functions on an intersecting family......Page 870
49.5 Intersection......Page 871
49.6 From an intersecting family to a lattice family......Page 872
49.7 Complexity......Page 873
49.8 Intersecting a polymatroid and a contrapolymatroid......Page 875
49.9 Submodular functions on a crossing family......Page 876
49.10 Complexity......Page 878
49.10a Nonemptiness of the base polyhedron......Page 879
49.11a Minimizing a submodular function over a subcollection of a lattice family......Page 880
49.11b Generalized polymatroids......Page 883
49.11c Supermodular colourings......Page 887
49.11d Further notes......Page 889
Part V: Trees, Branchings, and Connectors......Page 891
50.1 Shortest spanning trees......Page 893
50.2 Implementing Prim's method......Page 895
50.3 Implementing Kruskal's method......Page 896
50.3b A dual greedy algorithm......Page 897
50.4 The longest forest and the forest polytope......Page 898
50.5 The shortest connector and the connector polytope......Page 900
50.6a Complexity survey for shortest spanning tree......Page 902
50.6b Characterization of shortest spanning trees......Page 903
50.6c The maximum reliability problem......Page 904
50.6d Exchange properties of forests......Page 905
50.6e Uniqueness of shortest spanning tree......Page 906
50.6f Forest covers......Page 907
50.6g Further notes......Page 908
50.6h Historical notes on shortest spanning trees......Page 909
51.2 Disjoint spanning trees......Page 915
51.3 Covering by forests......Page 916
51.4 Complexity......Page 917
51.5a Complexity survey for tree packing and covering......Page 927
51.5b Further notes......Page 930
52.1 Finding a shortest r-arborescence......Page 931
52.2 Related problems......Page 933
52.3 A min-max relation for shortest r-arborescences......Page 934
52.4 The r-arborescence polytope......Page 935
52.4a Uncrossing cuts......Page 937
52.5 A min-max relation for longest branchings......Page 938
52.7 The arborescence polytope......Page 939
52.8b Concise LP-formulation for shortest r-arborescence......Page 940
52.8c Further notes......Page 941
53.1 Disjoint branchings......Page 942
53.2 Disjoint r-arborescences......Page 943
53.3 The capacitated case......Page 945
53.5 Covering by branchings......Page 946
53.6 An exchange property of branchings......Page 947
53.7 Covering by r-arborescences......Page 949
53.8 Minimum-length unions of k r-arborescences......Page 951
53.9 The complexity of finding disjoint arborescences......Page 956
53.10a Complexity survey for disjoint arborescences......Page 959
53.10b Arborescences with roots in given subsets......Page 961
53.10c Disclaimers......Page 963
53.10d Further notes......Page 964
54.1 Shortest R–S biconnectors......Page 966
54.2 Longest R–S biforests......Page 968
54.3 Disjoint R–S biconnectors......Page 969
54.5 Minimum-size bibranchings......Page 972
54.6 Shortest bibranchings......Page 973
54.6a Longest bifurcations......Page 975
54.7 Disjoint bibranchings......Page 978
54.7b Covering by bifurcations......Page 981
54.7d Covering by R–S biforests and by R–S bifurcations......Page 982
55.1 Minimum directed cut covers and packing directed cuts......Page 984
55.2 The Lucchesi–Younger theorem......Page 985
55.3 Directed cut k-covers......Page 987
55.4 Feedback arc sets......Page 989
55.5 Complexity......Page 991
55.5a Finding a dual solution......Page 992
55.6b Feedback arc sets in linklessly embeddable digraphs......Page 994
55.6c Feedback vertex sets......Page 996
55.6d The bipartite case......Page 997
55.6e Further notes......Page 998
56.1 Minimum directed cuts and packing directed cut covers......Page 1000
56.2 Source-sink connected digraphs......Page 1002
56.3 Other cases where Woodall's conjecture is true......Page 1005
56.3a Further notes......Page 1006
57.1 Making a directed graph strongly connected......Page 1007
57.2 Shortest strong connectors......Page 1008
57.4 Disjoint strong connectors......Page 1011
57.5 Complexity......Page 1013
57.5a Crossing families......Page 1014
58.1 The traveling salesman problem......Page 1019
58.3 Branch-and-bound techniques......Page 1020
58.4 The symmetric traveling salesman polytope......Page 1021
58.5 The subtour elimination constraints......Page 1022
58.6 1-trees and Lagrangean relaxation......Page 1023
58.7 The 2-factor constraints......Page 1024
58.8 The clique tree inequalities......Page 1025
58.8a Christofides' heuristic for the TSP......Page 1027
58.8b Further notes on the symmetric traveling salesman problem......Page 1028
58.9 The asymmetric traveling salesman problem......Page 1030
58.10a An integer programming formulation......Page 1031
58.10b Further notes on the asymmetric traveling salesman problem......Page 1032
58.11a Further notes......Page 1033
58.11b Historical notes on the traveling salesman problem......Page 1034
59.1 Introduction......Page 1043
59.2 The maximum size of a matching forest......Page 1044
59.3 Perfect matching forests......Page 1045
59.4 An exchange property of matching forests......Page 1046
59.5 The matching forest polytope......Page 1049
59.6a Matching forests in partitionable mixed graphs......Page 1053
59.6b Further notes......Page 1055
60.1 The Edmonds–Giles theorem......Page 1056
60.1b Generalized polymatroids and the Edmonds–Giles theorem......Page 1058
60.2 A variant......Page 1059
60.2a Applications......Page 1061
60.3a Lattice polyhedra......Page 1063
60.3b Polymatroidal network flflows......Page 1066
60.3c A general model......Page 1067
60.3d Packing cuts and Győri's theorem......Page 1068
60.3e Further notes......Page 1072
61.1 Orientations with bounds on in- and outdegrees......Page 1073
61.2 2-edge-connectivity and strongly connected orientations......Page 1075
61.2a Strongly connected orientations with bounds on degrees......Page 1076
61.3 Nash–Williams' orientation theorem......Page 1078
61.4 k-arc-connected orientations of 2k-edge-connected graphs......Page 1082
61.4b k-arc-connected orientations with bounds on degrees......Page 1083
61.4c Orientations of graphs with lower bounds on indegrees of sets......Page 1084
61.4d Further notes......Page 1085
62.1 Minimal k-(edge-)connected graphs......Page 1087
62.2 The network synthesis problem......Page 1089
62.3 Minimum-capacity network design......Page 1090
62.4 Integer realizations and r-edge-connected graphs......Page 1093
63.1 Making a directed graph k-arc-connected......Page 1096
63.1a k-arc-connectors with bounds on degrees......Page 1099
63.2 Making an undirected graph 2-edge-connected......Page 1100
63.3 Making an undirected graph k-edge-connected......Page 1101
63.3a k-edge-connectors with bounds on degrees......Page 1104
63.4 r-edge-connectivity and r-edge-connectors......Page 1105
63.5 Making a directed graph k-vertex-connected......Page 1112
63.6 Making an undirected graph k-vertex-connected......Page 1115
63.6a Further notes......Page 1116
Part VI: Cliques, Stable Sets, and Colouring......Page 1119
64.1 Terminology and notation......Page 1121
64.2 NP-completeness......Page 1122
64.3 Bounds on the colouring number......Page 1123
64.3b Hadwiger's conjecture......Page 1124
64.4a Facets and adjacency on the stable set polytope......Page 1126
64.5 Fractional stable sets......Page 1128
64.5a Further on the fractional stable set polytope......Page 1129
64.6 Fractional vertex covers......Page 1131
64.7 The clique inequalities......Page 1133
64.8 Fractional and weighted colouring numbers......Page 1134
64.8b The Chvátal rank......Page 1136
64.9a Graphs with polynomial-time stable set algorithm......Page 1137
64.9b Colourings and orientations......Page 1139
64.9c Algebraic methods......Page 1140
64.9d Approximation algorithms......Page 1141
64.9e Further notes......Page 1142
65.1 Introduction to perfect graphs......Page 1144
65.2 The perfect graph theorem......Page 1146
65.3 Replication......Page 1147
65.4 Perfect graphs and polyhedra......Page 1148
65.4a Lovász's proof of the replication lemma......Page 1149
65.5a 0- and 1-joins......Page 1150
65.5b The 2-join......Page 1151
65.6 Pre-proof work on the strong perfect graph conjecture......Page 1153
65.6a Partitionable graphs......Page 1154
65.6c The stable set polytope of minimally imperfect graphs......Page 1156
65.6d Graph classes......Page 1158
65.6e The P 4 -structure of a graph and a semi-strong perfect graph theorem......Page 1160
65.6f Further notes on the strong perfect graph conjecture......Page 1161
65.7a Perz and Rolewicz's proof of the perfect graph theorem......Page 1163
65.7b Kernel solvability......Page 1164
65.7c The amalgam......Page 1168
65.7d Diperfect graphs......Page 1169
65.7e Further notes......Page 1171
66.1 Bipartite graphs and their line graphs......Page 1173
66.2 Comparability graphs......Page 1175
66.3 Chordal graphs......Page 1176
66.3a Chordal graphs as intersection graphs of subtrees of a tree......Page 1180
66.4 Meyniel graphs......Page 1181
66.5a Strongly perfect graphs......Page 1183
66.5b Perfectly orderable graphs......Page 1184
66.5c Unimodular graphs......Page 1185
66.5d Further classes of perfect graphs......Page 1186
66.5e Further notes......Page 1187
67.1 Optimum clique and colouring in perfect graphs algorithmically......Page 1190
67.2 Weighted clique and colouring algorithmically......Page 1193
67.4a Further on θ(G)......Page 1197
67.4b The Shannon capacity Θ(G)......Page 1205
67.4c Clique cover numbers of products of graphs......Page 1210
67.4e An operator strengthening convex bodies......Page 1211
67.4f Further notes......Page 1213
67.4g Historical notes on perfect graphs......Page 1214
68.1 T-perfect graphs......Page 1224
68.2 Strongly t-perfect graphs......Page 1225
68.3 Strong t-perfection of odd-K 4 -free graphs......Page 1226
68.4 On characterizing t-perfection......Page 1232
68.5 A combinatorial min-max relation......Page 1234
68.6a The w-stable set polyhedron......Page 1238
68.6b Bidirected graphs......Page 1239
68.6c Characterizing odd-K 4 -free graphs by mixing stable sets and vertex covers......Page 1241
68.6d Orientations of discrepancy 1......Page 1242
68.6e Colourings and odd K 4 -subdivisions......Page 1244
68.6g Further notes......Page 1245
69.2 Maximum-size stable set in a claw-free graph......Page 1246
69.3 Maximum-weight stable set in a claw-free graph......Page 1251
69.4a On the stable set polytope of a claw-free graph......Page 1254
69.4b Further notes......Page 1255
Part VII: Multiflows and Disjoint Paths......Page 1257
70.1 Directed multiflow problems......Page 1259
70.2 Undirected multiflow problems......Page 1260
70.4 Reductions......Page 1261
70.5 Complexity of the disjoint paths problem......Page 1262
70.6 Complexity of the fractional multiflow problem......Page 1263
70.7 The cut condition for directed graphs......Page 1265
70.8 The cut condition for undirected graphs......Page 1266
70.9 Relations between fractional, half-integer, and integer solutions......Page 1268
70.10 The Euler condition......Page 1271
70.11 Survey of cases where a good characterization has been found......Page 1272
70.12 Relation between the cut condition and fractional cut packing......Page 1274
70.12a Sufficiency of the cut condition sometimes implies an integer multiflow......Page 1276
70.12b The cut condition and integer multiflows in directed graphs......Page 1279
70.13a Fixing the number of commodities in undirected graphs......Page 1280
70.13b Fixing the number of commodities in directed graphs......Page 1281
70.13c Disjoint paths in acyclic digraphs......Page 1282
70.13d A column generation technique for multiflows......Page 1283
70.13e Approximate max-flflow min-cut theorems for multiflows......Page 1285
70.13f Further notes......Page 1286
70.13g Historical notes on multicommodity flows......Page 1287
71.1 The Rothschild-Whinston theorem and Hu's 2-commodity flow theorem......Page 1289
71.1a Nash–Williams' proof of the Rothschild–Whinston theorem......Page 1292
71.2 Consequences......Page 1293
71.3 2-commodity cut packing......Page 1295
71.4a Two disjoint paths in undirected graphs......Page 1299
71.4b A directed 2-commodity flow theorem......Page 1300
71.4c Kleitman, Martin-Löf, Rothschild, and Whinston's theorem......Page 1301
71.4d Further notes......Page 1303
72.1 Demand graphs for which the cut condition is sufficient......Page 1304
72.2 Three commodities......Page 1309
72.2a The K 2,3 -metric condition......Page 1311
72.2b Six terminals......Page 1313
72.3 Cut packing......Page 1314
73.1 Disjoint T-paths......Page 1317
73.1a Disjoint T-paths with the matroid matching algorithm......Page 1321
73.1b Polynomial-time findability of edge-disjoint T-paths......Page 1323
73.1c A feasibility characterization for integer K 3 -flows......Page 1324
73.2 Fractional packing of T-paths......Page 1325
73.2a Direct proof of Corollary 73.2d......Page 1326
73.3a Further notes on Mader's theorem......Page 1327
73.3b A generalization of fractionally packing T-paths......Page 1328
73.3c Lockable collections......Page 1329
73.3d Mader matroids......Page 1330
73.3e Minimum-cost maximum-value multiflows......Page 1332
73.3f Further notes......Page 1333
74.1 All nets spanned by one face: the Okamura–Seymour theorem......Page 1334
74.1b Graphs on the projective plane......Page 1337
74.1c If only inner vertices satisfy the Euler condition......Page 1340
74.1d Distances and cut packing......Page 1342
74.1e Linear algebra and distance realizability......Page 1343
74.2 G + H planar......Page 1345
74.2a Distances and cut packing......Page 1346
74.2b Deleting the Euler condition if G + H is planar......Page 1347
74.3 Okamura's theorem......Page 1349
74.3a Distances and cut packing......Page 1351
74.3b The Klein bottle......Page 1352
74.3c Commodities spanned by three or more faces......Page 1354
74.4a Another theorem of Okamura......Page 1356
74.4c Vertex-disjoint paths in planar graphs......Page 1358
74.4d Grid graphs......Page 1361
74.4e Further notes......Page 1363
75.1 Weakly and strongly bipartite graphs......Page 1364
75.1b Planar graphs......Page 1366
75.2 Signed graphs......Page 1367
75.3 Weakly, evenly, and strongly bipartite signed graphs......Page 1368
75.4 Characterizing strongly bipartite signed graphs......Page 1369
75.5 Characterizing weakly and evenly bipartite signed graphs......Page 1372
75.6 Applications to multiflows......Page 1379
75.7 The cut cone and the cut polytope......Page 1380
75.8 The maximum cut problem and semidefinite programming......Page 1383
75.9a Cuts and stable sets......Page 1386
75.9b Further notes......Page 1388
76.1 Graphs, curves, and their intersections: terminology and notation......Page 1390
76.2 Making curves minimally crossing by Reidemeister moves......Page 1391
76.3 Decomposing the edges of an Eulerian graph on a surface......Page 1392
76.4 A corollary on lengths of closed curves......Page 1394
76.5 A homotopic circulation theorem......Page 1395
76.6 Homotopic paths in planar graphs with holes......Page 1399
76.7a Vertex-disjoint circuits of prescribed homotopies......Page 1405
76.7b Vertex-disjoint homotopic paths in planar graphs with holes......Page 1406
76.7c Disjoint trees......Page 1409
Part VIII: Hypergraphs......Page 1411
77.1 Elementary hypergraph terminology and notation......Page 1413
77.4 Clutters......Page 1414
77.6 The blocker......Page 1415
77.8 k-matchings and k-vertex covers......Page 1416
77.9a Bottleneck extrema......Page 1417
77.9b The ratio of τ and τ*......Page 1418
77.9c Further notes......Page 1419
78.1 Ideal hypergraphs......Page 1421
78.2 Characterizations of ideal hypergraphs......Page 1422
78.3 Minimally nonideal hypergraphs......Page 1424
78.4 Properties of minimally nonideal hypergraphs: Lehman's theorem......Page 1425
78.4a Application of Lehman's theorem: Guenin's theorem......Page 1430
78.4b Ideality is in co-NP......Page 1432
78.5b Further notes......Page 1433
79.1 Mengerian hypergraphs......Page 1435
79.1a Examples of Mengerian hypergraphs......Page 1437
79.2 Minimally non-Mengerian hypergraphs......Page 1438
79.3a Packing hypergraphs......Page 1439
79.3c Equivalences for k-matchings and k-vertex covers......Page 1440
79.3d A general technique......Page 1441
79.3e Further notes......Page 1442
80.2 Binary hypergraphs and binary matroids......Page 1444
80.3 The blocker of a binary hypergraph......Page 1445
80.4 On characterizing binary ideal hypergraphs......Page 1446
80.5 Seymour's characterization of binary Mengerian hypergraphs......Page 1447
80.5a Applications of Seymour's theorem......Page 1451
80.6a Oriented matroids......Page 1453
80.7a τ 2 (H) = 2τ(H) for binary hypergraphs H......Page 1454
80.7b Application: T-joins and T-cuts......Page 1455
80.7c Box-integrality of k · P H......Page 1456
81.1 Multiflows in matroids......Page 1457
81.2 Integer k-flowing......Page 1458
81.4 2-flowing and 2-cycling......Page 1459
81.5 3-flowing and 3-cycling......Page 1460
81.6 4-flowing, 4-cycling, ∞-flowing, and ∞-cycling......Page 1461
81.7 The circuit cone and cycle polytope of a matroid......Page 1462
81.9 Nonnegative integer sums of circuits......Page 1463
81.10 Nowhere-zero flows and circuit double covers in matroids......Page 1464
82.1 Elementary concepts......Page 1466
82.3 k-edge covers and k-stable sets......Page 1467
82.4 The antiblocker and conformality......Page 1468
82.5 Perfect hypergraphs......Page 1469
82.6a Some equivalences for the k-parameters......Page 1472
82.6b Further notes......Page 1475
83.1 Balanced hypergraphs......Page 1477
83.2 Characterizations of balanced hypergraphs......Page 1478
83.2a Totally balanced matrices......Page 1482
83.2c Balanced 0, ±1 matrices......Page 1485
83.3 Unimodular hypergraphs......Page 1486
83.3a Further notes......Page 1488
Survey of Problems, Questions, and Conjectures......Page 1491
References......Page 1501
Name Index......Page 1805
Subject Index......Page 1845
Greek graph and hypergraph functions......Page 1918
Back Cover......Page 1920