Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency (Springer-Verlag, Berlin, 2003)

This site contains corrections to, and other remarks on, the above book.
If you find more (whatever major or minor), please send them to lex@cwi.nl.
This site also includes an update of the "Survey of Problems, Questions, and Conjectures".
The corrections are also available as a postscript-file and a pdf-file.
The book is also available on CD-ROM from Springer-Verlag
This site was last modified on June 5, 2017.

Volume A:

• page VII, line 7 up: `Maffay' should be `Maffray'.
• page 6, line 9: `principal' should be `principle'.
• page 19, line 17: `form' should be `from'.
• page 20, line 1: delete `simple'.
• page 22, line 13 up: $(V,F)$ should be $(V,E)$.
• page 23, line 2: $V$ should be $C$.
• page 28, line 6: replace `graph' by `2-connected graph'.
• page 31, line 5: replace `The path' by `The walk'.
• page 32, line 13: replace `(3.13)' by `(3.58)'.
• page 38, line 2 up: g.c.d.$(p.q)$ should be g.c.d.$(p,q)$.
• page 49, line 18: replace `algorithms and algorithms' by `algorithms, and complexity'
• page 59, line 6 up: 7.1f should be 7.1j.
• page 60, line 10 up: `of and only if' should be `if and only if'.
• page 64, line 5: `... if and only if $F$ is nonempty and'
• page 64, Theorem 5.6: `inequalities' should be `equalities'.
• page 65, line 8: The Hirsch conjectue was disproved in 2010 by Francisco Santos, by a polytope in 43 dimensions with 86 facets (``A counterexample to the Hirsch conjecture'', arXiv:1006.2814v1).
• page 71, line 4: replace `polytope' by `full-dimensional pointed polyhedron'.
• page 71, lines 7, 10, 15: add `if any'.
• page 71, line 16: replace `14.1f' by `14.1g'.
• page 71, line 5 up: Add: `where $p$ is the polynomial in (5.32)(ii)'.
• page 71, line 3 up: Add before `such': `each of size at most $p(\text{size}(\sigma))$'.
• page 73, line 17 up: $\leq 0$ should be $\leq {\bf 0}$.
• page 76, line 7 up: replace `relation' by `relations'.
• page 80, Theorem 5.30: add the conditions that $A$ is integer and that $Ax\leq b$ defines a full-dimensional polyhedron, and replace $y^{\sf T}A\geq c^{\sf T}$ by $y^{\sf T}A=c^{\sf T}$.
• page 80, Theorem 5.31: $A'_1\leq b'_1$ should be $A'_1x\leq b'_1$.
• page 83, line 13 up: replace first and second $c$ by $f$.
• page 83, line 12 up: replace second $c$ by $f$.
• page 83, line 11 up: replace first $c$ by $f$.
• page 83, line 6 up: replace $c$ by $f$.
• page 87, abstract, line 4 up: add `solvable' after `polynomial-time'.
• page 89, (6.2): replace by: `delete all arcs entering $v$, and for each arc $a=(v,w)\in\delta^{\text{out}}(v)$: scan $w$.'
• page 93, line 14 up: delete `be'.
• page 100, line 2: `In proving (7.5), we may assume that $u$ is a root.' can be deleted.
• page 102, line 2 up: $-$ should be $+$.
• page 107, 11 up: `exists' should be `exist'.
• page 109, line 14: $d_n(v)$ should be $d_n(t)$.
• page 118, line 16 up: `length' should be `length,'.
• page 121, line 10: $L$ should be $N$.
• page 121, line 13: `to' should be `with'.
• page 124, line 9: `and C' should be `C'.
• page 125, line 12 up: add `,' before $n$.
• page 125, line 4 up and page 126, lines 1 and 2: replace $d_{i,j}$ by $c_{i,j}$ and $d_{j,i}$ by $c_{j,i}$.
• page 132, line 8: replace $S-C\cup\{u\}$ by $S-(C\cup\{u\})$.
• page 132, line 9: replace $C\cup\{v\}-T$ by $(C\cup\{v\})-T$.
• page 132, line 11 up: replace `is' by `if'.
• page 134, (9.3): replace $\delta_{A'}^{\mbox{\scriptsize\rm out}}= \delta_A^{\mbox{\scriptsize\rm out}}-1$ by $|\delta_{A'}^{\mbox{\scriptsize\rm out}}|= |\delta_A^{\mbox{\scriptsize\rm out}}|-1$.
• page 136, line 15: $D_f$ should be $D$.
• page 138, lines 2--3: $D_i$ should be $D_p$.
• page 139: all bounds on this page attributed to Nagamochi and Ibaraki [1992a] concern {\em undirected} graphs.
• page 144, lines 9--10: The hyphenation of `kapcsolatokra' is incorrect. Should be: `kap-csolatokra'.
• page 155, line 3: replace $t$ by $m'$ (twice).
• page 160, line 2: replace $t$ by $m'$ (twice).
• page 161, Research problem: This question was answered affirmatively by Jim Orlin, see: J.B. Orlin, Max flows in $O(nm)$ time, or better, in: {\em STOC'13 --- Proceedings of the 2013 ACM Symposium on Theory of Computing}, ACM, New York, 2013, pp. 765--774.
• page 167, line 10 up: `Fulkerson' should be `Fulkerson's'.
• page 177, line 11: Generality {\em is} lost by this assumption (as arcs can have different capacities and costs, so that they cannot be merged). The general case requires adaptation of running time bounds, like Orlin's bound on pages 189 and 191 becomes $O(m\log m SP_+(n,m,K))$ for the general case.
• page 195, line 16: replace $m^2/\log n$ by $m^2\log n$.
• page 195, line 17: Orlin [1997] gave a polynomial-time primal network simplex algorithm for minimum cost flow.
• page 196, line 8 up: `costs,see' should be `costs, see'
• page 198, line 15 up: replace `That is,' by `It also follows that'.
• page 204, line 1: `By the results above' is not clear. But it follows anyway from Theorem 13.8.
• page 205, line 9: replace `row' by `column'.
• page 207, lines 8, 12, 17: replace $|A|$ by $|V|$.
• page 209, (13.30): replace `out' by `in'.
• page 212, line 19: replace `Similarly for disjoint cuts' by `Similarly for the weighted case'.
• page 214, (13.47): this definition should be: $X_a:=\{s\in S \mid \pi(s)$ is contained in the weak component of $T-a$ containing $v\}$.
• page 215, line 20: `contains one of $\pi(x)$ and $\pi(y)$, say $\pi(y)$' should be `contains one of $x$ and $y$, say $y$'
• page 219, line 1: replace `Dilworth' by `Dilworth's'.
• page 222, Corollary 14.6a: delete $\uparrow$ (twice).
• page 223, line 16: `and' should be `end'.
• page 223, (14.9): replace $\delta$ by $\deg$.
• page 226, line 13: replace `arcs' by `arc'.
• page 238, line 12: (vertex-) should be on one line.
• page 242, line 13 up: replace `is' by `in'.
• page 245, line 10: replace `capacity' by `cardinality'.
• page 245, (15.11): replace $d(C)$ by $|C|$.
• page 250, line 15 up: replace `, Let' by `. Let'.
• page 251, line 2: delete `as'.
• page 251, Corollary 15.15a: replace `in time $O(n\tau)$ time' by 'in time $O(n\tau)$'.
• page 252, line 10 up: `adding ear' should be `adding an ear'.
• page 267, Section 16.7a: add: Here $f=\widetilde O(g)$ if $f=O(g\log^kg)$ for some $k$.
• page 275, lines 21 and 28--30: replace $D$ by $R$.
• page 278, line 19: `bizonyit\'as\'at' should be `bizony\'{\i}t\'as\'at'.
• page 281, line 16: `Januari' should be `January'.
• page 285, line 1 up: this line should be: `there exists a set $S\subseteq R$ containing no edge of $F$ and such that $|N_F(S)|<|S|$.'
• page 286, line 3: $\varepsilon$ should be $\alpha$.
• page 289, line 1 up: interchange $U$ and $W$.
• page 291, line 19 up: `algorithm' should be `algorithms'.
• page 299, line 1 up: replace $U_M$ by $W_M$.
• page 304, line 6 up: (18.10) should be (18.11).
• page 305, line 12 up: $\leq$ should be $\geq$.
• page 321, lines 18 up, 15 up and 9 up: replace $\chi$ by $\chi'$.
• page 323, first paragraph: This algorithm is not correct. One should choose $\lambda$ maximal such that $\lambda\leq c_e$ for each $e\in M$ and such that $\lambda\leq c(\delta(v))-c(\delta(u))$ for each vertex $v$ maximizing $c(\delta(v))$ and each vertex $u$ not covered by $M$. Then in each iteration either the number of edges of positive capacity drops, or it remains the same but then the number of vertices $v$ maximizing $c(\delta(v))$ drops.
• page 324, line 18 up: replace $\chi$ by $\chi'$.
• page 331, line 6: `match{\i}ng' should be `matching'.
• page 344, line 1: delete `,'.
• page 344, line 12: delete first `.'.
• page 347, line 1: `$x_{i,n}$ and $x_{m,j}$' should be `$x_{i,n}$, $x_{m,j}$, and $x_{m,n}$'
• page 361, (21.60): replace by: $\lfloor\alpha\deg_E(v)\rfloor \leq \deg_F(v) \leq \lceil\alpha\deg_E(v)\rceil.$
• page 367, table: replace $0+3=4$ by $0+3=3$.
• page 380, line 1: delete `the'.
• page 382, line 1 up: replace $\oZ_+$ by $\oZ_-$.
• page 383, line 9: replace `minimum' by `maximum'.
• page 391, line 2: `Januari' should be `January'.
• page 394, (23.4): last $\geq$ can be $=$.
• page 401, line 4: $({\cal A})$ should be $({\cal A},{\cal B})$.
• page 403, lines 7--3 up: This problem was solved by Weinberger [1976].
• page 413, line 6 up: replace `denotes' by `denote'.
• page 416, line 15: replace `path' by `walk'.
• page 423, line 7 after table: delete `.'.
• page 427, line 8 up: replace `. So' by `, and hence'.
• page 427, line 7 up: replace `, and ... barrier.' by `.'.
• page 433, line 9 up: replace `is' by `ist'.
• page 436, line 20: replace `1963' by `1961'.
• page 445, line 9 up: replace `matching' by `matchings'.
• page 447, (25.22): to prove that it determines a facet for $v\in I$, we can show that the vector $x:=\frac{1+\varepsilon}{\deg(v)}\chi^{\delta(v)}$ (for $\varepsilon>0$ small enough) satisfies all inequalities in (25.20) except (25.22)
• page 448, line 5: `with $u$ but not with $v$' should be `with $v$ but not with $u$'.
• page 448, line 7: $u$ should be $v$.
• page 465, line 8 up: $\chi(G)$ should be $\chi'(G)$.
• page 487, lines 20--24: this construction is incorrect. It can be corrected as follows. Make the original construction $G'$ as on page 487, except that you replace any negative-length edge $uv$ by edges $ux$, $u'x$, $xy$, $yv$, $yv'$, where $xy$ has weight $0$ and the other four edges each have weight $w(uv)/2$ (where $w(uv)$ is the length of the original edge). [For each negative-length edge we get two new vertices $x$ and $y$.] Then a minimum-length perfect matching in $G'-s-t$ gives a shortest $s-t$ path in $G$.
• page 501, line 12: $e\in T$ should be $e\in J$.
• page 501, lines 13 and 15: replace each $T$ by $J$.
• page 502, lines 3--4: Delete the sentence `So a $T$-border is a $T$-cut if and only if $\val(B)=1$.'
• page 502, Proof of Theorem 29.8: replace occurrences of `value' by `value at least'.
• page 502, line 13: add . after footnote 18.
• page 503, line 15 up: replace $G=\{u,w\}$ by $G-\{u,w\}$.
• page 504, line 20 up: add that $B$ has value $k/2$.
• page 504, line 18 up: add: `and as $|V'|=k\geq 4$'.
• page 504, line 10 up: multiply all terms in $|V'\setminus U|+o(G-U)\geq |V'|=k$ by $1/2$.
• page 510, line 3 up: replace $|J\triangle C|\geq |C|$ by $|J\triangle C|\geq |J|$.
• page 513, line 8: replace `leaves' by `enters'.
• page 514, lines 1--4: the `Conversely' part of the proof of Theorem 29.12 is not correct: an ear-decomposition of $G/F$ need not be the contraction of an ear-decomposition of $G$. See Szigeti [1996] for a counterexample to this and for a correct proof of the theorem.
• page 522, line 8--11: `equivalently ...' is not correct. Better to replace `equivalently ... 2-regular.' by: `Let $U$ be the set of vertices $v$ with $x(\delta(v))=1$. As $x$ is a vertex, $|U|\geq |E|$. Moreover, each vertex in $U$ has degree at least 2. Since $2|E|$ is equal to the sum of the degrees, it follows that each degree is 0 or 2.'
• page 526, (30.14): $u'p_{e,u},u'p_{e,u}$ should be $u'p_{e,u},u''p_{e,u}$.
• page 533, lines 13--5 up: From `So' on, replace by: `So $|E|\leq |U|$. Then each vertex in $U$ of degree 1 has its neighbour in $V\setminus U$ (as $G$ is connected and has at least three vertices). So the sum of the degrees of all vertices of $G$ is at least $2|U|$, which is at least $2|E|$. Hence these inequalities are tight, and therefore $G$ is either a star or a circuit. If $G$ is a star, then $x_e=1$ for each edge $e$. If $G$ is a circuit, then $\frac12\cdot{\bf 1}$ satisfies all constraints that $x$ satisfies, implying $x=\frac12\cdot{\bf 1}$, as $x$ is a vertex.'
• page 536, inequalities (iii) in (30.51) and (30.52): they should read: $$x(E[U]) + x(\delta(U)\setminus F) \geq |U| - \lfloor \frac12 |F| \rfloor.$$
• page 540, line 11: replace 1 by 2.
• page 544, (30.85): replace by: $G$ has a perfect 2-matching in which each circuit has length larger than $k$ if and only if for each $S\subseteq V$, the graph $G-S$ has at most $|S|$ $P_k$-critical components.
• page 545, (30.87): this was proved by Cornu\'ejols, Hartvigsen, and Pulleyblank [1982].
• page 545, line 11: delete `also'.
• page 549, lines 3, 2, 1 up: add `simple' before `$b$-matching'. Move these lines to page 574.
• page 550, (31.19): $\chi^{E[U]}$ should be $z(U)\chi^{E[U]}$.
• page 550, (31.20): $y'_v(v)$ should be $y'_vb(v)$.
• page 574: Move the last three lines of page 549 to this page.
• page 584, line 4: `lower{\em or}' should be `lower {\em or}'.
• page 587, line 9 up: $F$ should be $F'$.
• page 593, line 9: replace $l:E\to\oQ$ by $l:E\to\oQ_+$.
• page 610, line 11: $1 < |U| < |U|-1$ should be $1 < |U| < |V|-1$.
• page 640, line 14: `AND THat' should be `and that'.

Volume B:

• page 653, line 15: `in independent' should be `is independent'.
• page 668, line 5: $\span_M(F)$ should be $\span_M(F+t)$.
• page 673, line 16: bases should be base.
• page 707, lines 19--20: replace `polynomial' by `exponential'.
• page 709, lines 6, 4, 3 up: replace $J$ by $I'$.
• page 733, Proof of Theorem 42.6: Assume without loss of generality that $M$ has no loops (otherwise, no such $\lambda$ may exist).
• page 733, line 4 up: replace 51.7 by 42.6.
• page 734, Proof of Theorem 42.7: we may assume that the initial $y$ does not belong to $P_{\text{spanning set}}(M)$ and that ${\mathbf 0}\leq y\leq{\mathbf 1}$. In the iterations, as soon as $y'$ does not satisfy $y'\leq{\mathbf 1}$, $L$ does not intersect $P_{\text{spanning set}}(M)$, and hence no $\lambda$ as required exists (because if $\lambda y\in P_{\text{spanning set}}(M)$, then for each $v\in S$: $y'_v=\frac{r(S)-r(U)}{y(S\setminus U)}y_v \leq\lambda y_v\leq 1$, since $r(S)-r(U)\leq \lambda y(S\setminus U)$, as $\lambda y\in P_{\text{spanning set}}(M)$).
• page 738, line 13: delete `is'.
• page 740, lines 1--2: replace $p_1$ and $p_2$ by $\pi_1$ and $\pi_2$.
• page 740, lines 5, 6, 7, and 9: replace $S$ by $U$. ($S$ is the ground set of the matroid.)
• page 747, line 13 up: add `if $M$ is a base' before `.'.
• page 758, line 21: $C(M,E)$ should be $C(M,e)$.
• page 774, line 10: replace $T$ by $U$.
• page 775, line 20: replace `submodular' by `supermodular'.
• page 779, line 14 up: interchange $T\cup U$ and $T\cap U$.
• page 784, line 5: replace $V$ by $S$.
• page 784, line 15: replace (first) $U$ by $U\setminus\{v\}$.
• page 784, line 16: replace $N_F(U)$ and $N_F(\{v\})$ by $|N_F(U)|$ and $|N_F(\{v\})|$.
• page 795, line 1: replace `nice' by `nicely'.
• page 795, line 5 up: replace $\mid\mid$ by $\mid$.
• page 780, line 13: replace $s\in S$ by $s\in U$.
• page 799, line 6: replace `submodular' by `supermodular'.
• page 820, line 4: $x(\emptyset) < f(\emptyset)$ should be $x(\emptyset)\leq f(\emptyset)$.
• page 824, (48.21)(ii): add: `with $|U| \geq 2$'.
• page 827, line 12: replace $\mathcal{C}$ by $S$.
• page 851, line 20: $f((S\setminus X)\cup Y)$ should be $f(S\setminus X,Y)$.
• page 854, line 6: `edge' should be `edges'.
• page 859, line 14 up: delete $\in$.
• page 871, line 17: `belance' should be `balance'.
• page 873, line 13: `concerned on' should be `concerned with'.
• page 880, first line of (51.13): replace the second $y_v>0$ by $y_v<0$.
• page 886, line 2 up: `holds' should be `hold'.
• page 887, Proof of Theorem 51.8: Adapt the proof similarly to the adaptation of the Proof of Theorem 42.7 (page 734) given above.
• page 890, line 7 up: `problem' should be `problems'.
• page 891, line 17: `forest' should be `forests'.
• page 892, line 10: the case $k=4$ of (51.44) for $4$-connected graphs was proved by S. Curran, O. Lee, and X. Yu, Chain decompositions and independent trees in 4-connected graphs, in: {\em Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms} (Baltimore, Maryland, 2003), ACM, New York, 2003, pp. 186--191.
• page 895, line 8 up: add `giving D'$ after `of length 0$'.
• page 897, (52.6): add: (iv) $x(\delta^{\text{in}}(r))=0$.
• page 898, Proof of Theorem 52.4: This proof should reduce to Theorem 46.4 instead of Corollary 46.1d. It requires replacing (52.10) by the system corresponding to (46.28). A direct and more transparant proof is given in Section 52.4a.
• page 907, line 11: `term' should be `terms'.
• page 910, (53.17): $B_1\cup B_1$ should be $B_1\cup B_2$.
• page 911, Theorem 53.3: `covered by' should be `partitioned into'.
• page 912, line 3 up: `throughout,' should be `throughout.'
• page 920, line 7 up: add $d(R_1)$ to the domain of the minimum for $\mu$.
• page 920, line 1 up: replace $\delta^{\text{\rm in}}(W)$ by $\delta^{\text{\rm in}}(W')$.
• page 921, line 1: replace $W\cap R_1$ by $W'\cap R_1$, and $\delta_{A'}^{\text{in}}(W)$ by $\delta_{A'}^{\text{in}}(W')$.
• page 921, line 11: replace $|A|+|V|^3$ by $|\mathcal{R}|+|A|+|V^3|$.
• page 921, line 7 up: replace $\delta$ by $d$.
• page 932, line 6 up: add `is' before `because'.
• page 933, line 3: `tree' should be `trees'.
• page 946, line 3 of abstract: replace `equivalent' by `equivalently'.
• page 947, line 4 up: `graph' should be `digraph'.
• page 952, caption Figure 55.1: `disjoint directed cuts' should be `arc-disjoint directed circuits'.
• page 952, line 3: delete `is done'.
• page 952, caption Figure 55.2: `disjoint directed cuts' should be `arc-disjoint directed circuits'.
• page 952, line 8 up: `subhypergraph' should be `subdigraph'.
• page 964, line 3 up: $B_i'\cup B'_i$ should be $B_i'\cup B_i''$.
• page 965, line 2 up: $C^{-1}$ should be $C'^{-1}$.
• page 966, line 3: delete `of'.
• page 969, first line of Section 57.1: add `$D=$ before $(V,A)$.
• page 985, line 1: replace `for any length function' by `both in the symmetric and the asymmetric case'.
• page 986, line 9: `inequality' should be `equality'.
• page 988, line 5 up: `know' should be `known'.
• page 992, line 6 up: replace $|U|-2$ by $|V|-2$.
• page 993, line 6: replace `directed $1$-tree' by `$1$-arborescence'.
• page 996, line 21 up: delete `method'.
• page 997, line 8: replace `A' by `An'.
• page 997, line 10: replace `a' by `an'.
• page 1004, line 1: `run' should be `ran'.
• page 1019, line 13: replace $z,u,y$ by $y$.
• page 1022, (60.16): replace $\geq$ by $\leq$.
• page 1025, (60.25): add $(u)$ after $\chi^{\phi(a)}$ (twice).
• page 1037, Proof of Theorem 61.3: start with `We can assume that $G$ is connected.'
• page 1038, line 12: replace `$s$ to $t$' by `$u$ to $v$'.
• page 1038, line 15: add `in' between $e$ and $\delta(T)$.
• page 1038, line 5 up: replace `for each $U\subseteq V$' by `for each nonempty $U\subseteq V$'.
• page 1041, line 1 up: add: `if $d_G(X)$ is even or $d_G(X)$ is minimal over all $X$ splitting $Y$'.
• page 1042, line 6: $V$ should be $V_1$.
• page 1042, line 10: delete `and for ... $V_2\setminus U$'.
• page 1042, lines 17--19: replace sentence by: `To show this, we may assume that $$r_Y(U\cap X)^* + r_Y(U\cup X)^* \geq r_Y(U)^* + r_Y(X)^*$$ and $$d_P(U\cap X) + d_P(U\cup X) \geq d_P(U).$$ Indeed, the first inequality follows from (61.23), as we can replace $U$ by $V\setminus U$. Suppose the second inequality does not hold. Then $d_G(X)$ is odd and $u_1\in X\setminus U$, $u_2\in U\setminus X$. This implies $$r_Y(X\setminus U)^* + r_Y(U\setminus X)^* \geq r_Y(U)^* + r_Y(X)^*$$ (since $r_Y(X) = \lambda_G(u,v)$ for all $u,v$ split by $X$, and since $X\setminus U$ and $U\setminus X$ are nonempty). So we can replace $U$ by $V\setminus U$.'
• page 1042, line 13 up: add: `with $d_G(U)$ even'.
• page 1042, line 8 up: replace $r(U)^*$ by $r'(U)^*$, where $r'(U)$ denotes the maximum of $\lambda_{G'}(u,v)$ over $u,v\in X$ split by $U$.
• page 1043, lines 13--15: delete this sentence.
• page 1043, line 16 up: (61.34) should be (61.24).
• page 1043, line 15 up: add after `that is,': `we may assume'.
• page 1043, after (61.35): add: `(Note that $r_Y(U)=r_Y(X)$, since $U\cap Y = U\cap X$.)'
• page 1047, line 15: replace 11.2f by 11.2g.
• page 1051, line 10 up: replace $G$ by $D$.
• page 1059, (63.7): exchange $T$ and $U$.
• page 1061, Theorem 63.3: replace `an undirected graph' by `a directed graph'.
• page 1069, line 12 up: replace $X\cup Y$ by $(V\cup \{s\})\setminus (X\cup Y)$.
• page 1069, line 6 up: replace $d(X\cap Y,V\setminus (X\cup Y))$ by $|E(X\cap Y,(V\cup \{s\})\setminus (X\cup Y))|$.
• page 1079, line 16 up: replace `Jordan' by `Jord\'an'.
• page 1082, line 13: replace `of' by `or'.
• page 1088, line 1 up: delete `unique'.
• page 1089, lines 10--12: replace by `This proves (64.7).'
• page 1092, line 5 up: Add `is' before `integer'.
• page 1097, (64.42): add `if' after `only'.
• page 1098, line 7: delete `Set $k:=\alpha(G)$.'.
• page 1107, line 3: replace `te' by `to'.
• page 1107, lines 8--7 up: Polynomial-time algorithms recognizing perfect graphs were found in 2002 by M. Chudnovsky, G. Cornu\'ejols, X. Liu, P.D. Seymour, and K. Vu\v{s}kovi\'c.
• page 1120, line 3: `nonnegative' should be `nonnegativity'.
• page 1129, (65.49): `exist' should be `exists'.
• page 1144, line 4: `its' should be `it'.
• page 1150, lines 10--11: `classes some' should be `some classes'.
• page 1151, lines 10--11: replace `from Dilworth's decomposition theorem' by `in the same way as Theorem 14.1'.
• page 1153, second line of (67.5): $C_1$ should be $C_i$.
• page 1160, (67.28): replace $\geq$ by $\leq$ (twice).
• page 1160, line 14 up: replace $C$ by $-C$.
• page 1160, line 13 up: replace $\geq$ by $\leq$.
• page 1160, line 6 up: replace $C$ by $-C$.

Volume C:

• page 1223, (70.5): $G$ should be $D$.
• page 1225, footnote 4: this is not due to Kramer and van Leeuwen [1984], but to P. Raghavan, Randomized rounding and discrete ham-sandwich theorems: provably good algorithms for routing and packing problems. Ph.D.\ thesis, Report No.\ UCB/CSD 87/312, University of California, Berkeley, California, 1986.
• page 1233, line 2 up: replace `that is' by `in particular'.
• page 1235, first line of caption of Figure 70.6: `with D+H is planar' should be `with D+H planar'.
• page 1239, running head: `Sofficiency' should be `Sufficiency'.
• page 1241, (70.50): replace each $a$ by $a'$.
• page 1253, line 5: replace $\frac12( |g'(a)| + |g''(a)| )$ by $\max \{ |g'(a)| , |g''(a)| \}$.
• page 1255, line 6: delete `a'.
• page 1255, line 4--2 up: delete the sentence `So $M$ is equal ... and $t_2$.'
• page 1282, line 4 up: add `internally' before `disjoint'.
• page 1289, line 7: `an' should be `a'.
• page 1293, (73.52): this question was answered positively by G. Pap (February 2006).
• page 1294, (73.54): this question was answered positively by G. Pap (February 2006).
• page 1299, line 10--8 up: in April 2007, this edge-disjoint paths problem problem was shown to be NP-complete by W. Schw\"arzler (On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary, Combinatorica 29 (2009) 121--126).
• page 1317, line 21 up: `was' should be `way'.
• page 1323, lines 7--6 up: NP-completeness of the edge-disjoint paths problem for grid graphs was proved by P. Raghavan [1986] (see reference given above (at page 1225)).
• page 1378, (77.15): replace ${\cal F}$ by ${\cal E}$.
• page 1382, line 10: replace $\nu(H)=\nu$ by $\tau(H)=\tau$.
• page 1395, line 19: replace `65.2' by `78.5'.
• page 1400, line 3 up: add 8 inbetween 7 and 9.
• page 1401: delete the first four lines.
• page 1408, (80.5)(iii) and (iv): replace $E\in H$ by $E\in{\cal E}$.
• page 1423, (81.16)(ii): replace `is, is' by `is,'.
• page 1424, (81.19)(ii): replace $M$ by $M^*$.
• page 1425, (81.21)(ii): replace $M$ by $M^*$.
• page 1429, (82.4) and (82.9): replace ${\cal F}$ by ${\cal E}$.
• page 1440, lines 1, 2, and 10 up: balancedness is not closed under parallelization. The implication (i)$\Rightarrow$(v) in (83.3) follows by taking a partition of $V$ into $r:=r_{\max}(H)$ classes $S_1,\ldots,S_r$ such that the number of pairs $S_i,E$ with $1\leq i\leq r$, $E\in\cal{E}$, and $S_i\cap E\neq\emptyset$ is maximized. Suppose now that $|S_i\cap E|\geq 2$ for some $i$ and $E\in\cal{E}$. Then $|S_j\cap E|=0$ for some $j$. By (83.4) we can split $S_i\cup S_j$ into $S'_i$ and $S'_j$ such that both $S'_i$ and $S'_j$ intersect each edge that intersects $S_i\cup S_j$ at least twice. Replacing $S_i,S_j$ by $S'_i,S'_j$ would increase the above number, a contradiction.\\ This proves (i)$\Rightarrow$(v). Then (i)$\Rightarrow$(ii) follows from Theorem 82.4, and (i)$\Rightarrow$(ii) by symmetry.
• page 1442, line 3: balancedness is not closed under parallelization. The implication (i)$\Rightarrow$(iv) in (83.5) can be derived from (iii) and (vii) as follows. Let $w:V\to\oZ_+$. We must show that \begin{equation} \label{MAX} \max\{y^{\sf T}{\bf 1}\mid y\geq{\bf 0}, y^{\sf T} M\leq w^{\sf T}\} \end{equation} has an integer optimum solution, where $M$ is the ${\cal E}\times V$ incidence matrix of $H$. Choose a counterexample with $|{\cal E}|+w^{\sf T}{\bf 1}$ minimal. Since $H$ is ideal and by complementary slackness, any optimum solution $y$ of (\ref{MAX}) satisfies $y^{\sf T} M=w^{\sf T}$ (otherwise we can decrease some component of $w$ by one). Moreover, $y>{\bf 0}$ (otherwise we can delete some edge). By (vii), $$\min\{z^{\sf T}{\bf 1}\mid z\geq{\bf 0}, z^{\sf T} M\geq w^{\sf T}\}$$ has an integer optimum solution $z$. So $z^{\sf T}{\bf 1}\leq y^{\sf T}{\bf 1}$. For $\varepsilon>0$ small enough, $y':=y+\varepsilon(y-z)$ satisfies ${y'}^{\sf T}{\bf 1}\geq y^{\sf T}{\bf 1}$, $y'\geq{\bf 0}$, ${y'}^{\sf T} M\leq w^{\sf T}$. So $y'$ is again an optimum solution of (\ref{MAX}), hence $z^{\sf T}{\bf 1}=y^{\sf T}{\bf 1}$ and $z^{\sf T} M=w^{\sf T}$. So $z$ is an integer optimum solution of (\ref{MAX}).
• Survey of Problems, Questions, and Conjectures:
  • page 1453, problem 3: The Hirsch conjectue was disproved in 2010 by Francisco Santos, by a polytope in 43 dimensions with 86 facets (``A counterexample to the Hirsch conjecture'', arXiv:1006.2814v1).
  • page 1453, problem 4: This question was answered affirmatively by Jim Orlin, see: J.B. Orlin, Max flows in $O(nm)$ time, or better, in: {\em STOC'13—Proceedings of the 2013 ACM Symposium on Theory of Computing}, ACM, New York, 2013, pp. 765--774.
  • page 1453, problem 6: was solved by Weinberger [1976].
  • page 1456--1457, problem 32: the case $k=4$ of (16) for $4$-connected graphs was proved by S. Curran, O. Lee, and X. Yu, Chain decompositions and independent trees in 4-connected graphs, in: {\em Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms} (Baltimore, Maryland, 2003), ACM, New York, 2003, pp. 186--191.
  • page 1457, problem 35: The length function should satisfy the triangle inequality. It is also an open problem for the directed case.
  • page 1458, problem 42: Polynomial-time algorithms recognizing perfect graphs were found in 2002 by M. Chudnovsky, G. Cornu\'ejols, X. Liu, P.D. Seymour, and K. Vu\v{s}kovi\'c.
  • page 1459, problem 54: was answered positively by G. Pap (February 2006).
  • page 1459, problem 55: was answered positively by G. Pap (February 2006).
  • page 1459, problem 56: in April 2007, this edge-disjoint paths problem problem was shown to be NP-complete by W. Schw\"arzler (On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary, Combinatorica 29 (2009) 121--126).
• page 1478, line 6: replace `Jordan' by `Jord\'an'.
• page 1480, line 10, page 1491, line 21, page 1512, line 8 up, page 1526, line 1, page 1530, lines 6--7, page 1548, line 12 up, page 1558, line 11, page 1562, line 17, page 1582, line 2 up, page 1656, line 21 up, page 1692, line 15 up, page 1726, line 20: replace `Engineering' by `Administration'.
• page 1812, right column, line 12 up: `callection' should be `collection'.

Thanks to Nir Alfasi, Nikos Apostolou, Marcia Cerioli, Eric Colin de Verdi\`ere, Denis Cornaz, Bill Cunningham, Diana Fanghaenel, Kyle Fox, Andr\'as Frank, Takuro Fukunaga, Dion Gijswijt, Michel Goemans, Neboj\v{s}a Gvozdenovi\'c, Willem-Jan van Hoeve, Chien-Chung Huang, Garth Isaak, Tibor Jord\'an, Vincent Jost, Maurice Jutte, Naoyuki Kamiyama, Andreas Karrenbauer, Paulien van Katwijk, Judith Keijsper, Zoltan Kir\'aly, Petr Kolman, Wouter Koolen-Wijkstra, Peter Korteweg, Lap Chi Lau, Monique Laurent, Mario Leston, Misha Lomonosov, Marci Makai, G\'abor Mar\'oti, Tom McCormick, Sanjay Melkote, Fernando Mario de Oliveira Filho, Shay Mozes, Gianpaolo Oriolo, Marc Pfetsch, Coelho de Pina, Bill Pulleyblank, Tadashi Sakuma, Andr\'as Seb\H{o}, Bruce Shepherd, Marcel Silva, Jacint Szabo, Laci Szeg\H{o}, D\'avid Szeszl\'er, Zoli Szigeti, Shin-ichi Tanigawa, Jens Vygen, Christophe Weibel, Aaron Williams, Giacomo Zambelli, Francisco J. Zaragoza, and Uri Zwick.

Table of Contents
Survey of Problems, Questions, and Conjectures
Comments welcome at lex@cwi.nl
Further Information from Springer-Verlag Heidelberg
Further Information from Springer-Verlag New York

---

CWI DISCLAIMER

---