AI Glossary / Graphs and symbolic AI / Intermediate

Boykov-Kolmogorov

Definition

Boykov-Kolmogorov is an algorithm for computing maximum flow between a source and a sink in a capacitated graph. Through the maximum-flow/minimum-cut relationship, it also supports finding a minimum cut separating those terminals. It is especially associated with graph-based energy minimization in computer vision, where suitable labeling problems can be represented as cuts.

What it means

A graph describes connections, and capacities limit how much flow can pass along them. The maximum-flow problem asks for the largest total transfer from a designated source to a sink while respecting capacities and conserving flow at intermediate nodes. A minimum cut identifies a partition whose crossing capacity limits that transfer.
In image analysis, the graph can encode preferences for assigning pixels to labels rather than literal fluid movement. Solving the resulting cut problem optimizes that encoded objective. The algorithm does not itself decide which graph accurately represents an image, and not every vision objective can be represented by a single exact minimum cut.

How it works

The method maintains search trees associated with the source and sink in the residual graph, which records remaining capacity and possible reversals of previous flow. During growth, the trees expand until they connect through an augmenting path. Augmentation sends additional flow along that path, limited by its smallest residual capacity.
Some tree links then become unusable because their residual capacity is exhausted. An adoption stage repairs the trees where possible instead of discarding all search structure and starting again. These stages repeat until no further augmenting connection exists. Reusing the trees is a defining practical feature; actual speed depends on the graph and implementation.

Three practical examples

• A binary image-segmentation model uses a minimum cut to divide pixels into two labels when its objective has the required graph representation.
• A network analysis tool computes a source-to-sink capacity limit and examines a corresponding bottleneck cut.
• A vision researcher uses the algorithm as the flow solver inside a larger energy-minimization procedure, while separately checking what that outer procedure guarantees.

Think of it this way

Think of two crews extending connected paths from opposite ends of a transport network. When their paths meet, they send more cargo through, then repair routes whose capacity has been used. The analogy helps explain tree reuse. Residual reverse edges, however, are bookkeeping for revising earlier decisions; they need not represent physical reverse transport in the original network.

Worked example

Consider a directed graph with edges s to a of capacity 4, s to b of capacity 3, a to t of capacity 2, b to t of capacity 4, and a to b of capacity 2. One feasible flow sends 2 units along s-a-t, 3 along s-b-t, and 1 along s-a-b-t.
The total is 6. Edge s-a carries 3 of its 4-unit capacity, s-b carries 3 of 3, a-b carries 1 of 2, a-t carries 2 of 2, and b-t carries 4 of 4. Flow is conserved at a and b. The cut with {s, a, b} on one side and {t} on the other has capacity 2 + 4 = 6. Therefore no flow can exceed 6, and the displayed flow is maximum. This is a result check, not a claim that a particular implementation must choose these augmenting paths in this order.

Illustrative case study

At fictional Cedar Imaging, engineers encode a small foreground/background task as a graph and use a Boykov-Kolmogorov implementation to solve the cut. They inspect both the optimization result and whether the chosen pixel penalties match the intended segmentation behavior.
A mathematically optimal cut that follows an unwanted boundary leads them to revisit the model, rather than accuse the solver of failing to optimize it. The fictional case illustrates the separation between solving a graph correctly and defining a useful image objective. No accuracy or speed improvement is claimed.

Common misconceptions and mistakes

Boykov-Kolmogorov is not a neural network and does not learn image features by itself. Maximum flow is also different from minimum-cost flow: capacities alone do not introduce a cost per transported unit.
An exact minimum cut does not imply an exact solution to every larger vision problem that uses cuts as substeps. Historical performance on vision graphs does not establish that this algorithm is fastest on every graph. In software, pay attention to return types and stopping options: the NetworkX routine returns a residual network, and an early cutoff can prevent immediate determination of a minimum cut.

Business use

The method is relevant when a business problem can be represented as a suitable flow or cut model, especially inside image-processing tools. Selection should consider graph structure, memory, implementation quality, and reproducible benchmarks. An operational review should also check capacities and the meaning of the objective. A missing capacity or incorrectly constructed edge can change the mathematical problem while still producing a plausible-looking answer.

People also ask

Does the algorithm work only on images?

No. It solves a graph flow problem, although computer vision motivated important applications and evaluations.

Is the flow solution always unique?

No. Different feasible flow assignments can attain the same maximum value.

Does a cutoff certify the maximum?

Not necessarily. Reaching a requested threshold can stop computation before the complete maximum-flow/minimum-cut result is established.

Check your understanding

A feasible flow has value 6 and a separating cut has capacity 6. What does that prove?

Answer: The flow is maximum and the cut is minimum for that graph, because a flow cannot exceed a separating cut's capacity.

Related terms

• Maximum Flow
• Image segmentation
• minimum cut
• residual graph
• augmenting path
• graph cut
• energy minimization

Learn next

Draw the worked graph and verify capacity and conservation constraints edge by edge. Then change one terminal-edge capacity and reconsider the cut bound. This connects the algorithm's output to a checkable certificate rather than relying solely on a software result.

More in Graphs and symbolic AI

• Bounded suboptimal search - Bounded suboptimal search seeks a feasible solution whose cost is guaranteed to stay within a specified amount of the optimal cost.
• Bounds consistent - Bounds consistent describes a constraint whose remaining domain endpoints each have a supporting assignment under the chosen definition of bounds consistency.
• Bounds propagation - Bounds propagation is the repeated tightening of variables' lower and upper limits using constraints.
• Branching factor - Branching factor is the number of immediate successor choices available from a node in a search tree. It describes how widely a search can expand at each step.
• Breadth First Search - Breadth First Search, usually written breadth-first search or BFS, explores a graph in layers outward from a starting node.
• Breadth First Search on Edges - Breadth First Search on Edges is a breadth-first graph traversal that reports encountered edges, including edges leading to nodes already discovered.

Sources

Sources: NetworkX, official Boykov-Kolmogorov documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.boykov_kolmogorov.html . Boykov and Kolmogorov, original paper and author abstract: https://www.csd.uwo.ca/~yboykov/Abstracts/pami04-abs.html . Original paper repository: https://discovery.ucl.ac.uk/id/eprint/13383/1/13383.pdf .

Previous: Boyce-Codd Normal Form Next: Bracketed notation