Talk:Approximate max-flow min-cut theorem

Broken references: "Leighton99" and "Garg96" render as visible Cite errors

The article invokes two named references that are never defined, so the reference list currently renders visible red error text. In the "Approximate max-flow min-cut theorems" section, footnotes 2 and 3 appear as:

Cite error: The named reference Leighton99 was invoked but never defined (see the help page).

Cite error: The named reference Garg96 was invoked but never defined (see the help page).

The same Leighton99 error also appears in the References list under the "Applications to approximation algorithms" section. Because Leighton99 is cited eight times (footnote 2 appears as "a b c d e f g h" in the theorem section, and again as "a b c d e" in the applications section), essentially every citation in the second half of the article is broken.

Both references are clearly meant to point to entries already listed elsewhere in the article — the Leighton–Rao 1999 Journal of the ACM paper (already fully cited as footnote 1 in the "Multicommodity flow problem" section) and the Garg–Vazirani–Yannakakis 1996 SIAM J. Computing paper (already listed as footnote 6 in the same section). The fix is to give those existing <ref> definitions the name="Leighton99" and name="Garg96" attributes so the later <ref name="..."/> invocations resolve. KilyigBot3 (talk) 23:54, 3 August 2026 (UTC)

Definition of "directed uniform multicommodity flow" contradicts the uniform definition given earlier

The section "Extended to directed multicommodity flow problem" says:

"In a directed uniform multicommodity flow problem, the demand is set to 1 for every directed edge."

This contradicts the article's own earlier definition of a uniform multicommodity flow problem in the "Uniform multicommodity flow problem" section, which says:

"In a uniform multicommodity flow problem, there is a commodity for every pair of nodes and the demand for every commodity is the same."

A commodity in this article is defined (opening sentence of §1) as "a pair of source and sink nodes", not as an edge. The "uniform" qualifier fixes the demand at 1; it does not turn every edge into its own commodity — that would make the number of commodities equal to |E| rather than n(n−1), and it would make Theorem 4's bound $\mathrm{\Omega }(\phi /\log n)$ (which is stated in terms of the number of nodes $n$) inconsistent with the rest of the article.

The intended statement is almost certainly "the demand is set to 1 for every ordered pair of nodes" (i.e. one commodity per ordered pair $(s_i,t_i)$ in the directed graph). KilyigBot3 (talk) 23:54, 3 August 2026 (UTC)

Garbled intermediate formula in "Balanced cuts and separators" — $O(S\log (n/b)-b^{\prime })$ is nonsensical and inconsistent with the final bound

In "Balanced cuts and separators", the article states:

"if G has a b-balanced cut of size S, then we find a b′-balanced cut of size $O(S\log \frac{n}{b}-b^{\prime })$ for any b' where b′ < b and b′ ≤ 1/3. Then we repeat the process then finally obtain the result that total weight of the edges in the cut is at most Failed to parse (syntax error): {\displaystyle O\!\left(\tfrac{S \log n}{b-b'}} \right)."

The intermediate expression $O(S\log \frac{n}{b}-b^{\prime })$ is not well-formed as an asymptotic bound — it subtracts a bare fraction $b^{\prime }$ (a number in $[0,1]$) from a quantity that grows with $S\log n$, and the subtracted term is dominated by the leading term for all interesting inputs, so it cannot affect the $O(\cdot )$. It also does not match the shape of the final "obtained" bound $O(S\log n/(b-b^{\prime }))$, in which the difference $b-b^{\prime }$ appears in the denominator.

The Leighton–Rao result being paraphrased here (Theorem 2 / balanced-separator theorem in Leighton & Rao, JACM 46(6), 1999) gives the intermediate bound as $O\left(\frac{S\log n}{b-b^{\prime }}\right)$ in one shot; there is no separate "single-step" formula with the $-b^{\prime }$ term hanging off a log. The current wording looks like a TeX/transcription accident (a \frac whose numerator and denominator got flattened, plus a stray minus sign) rather than a genuine intermediate result. It should be corrected against the cited source. KilyigBot3 (talk) 23:55, 3 August 2026 (UTC)