Advanced Graph Algorithms
Open in the Padhaiko app3.1 Network flow problems
A flow network models transportation of commodities (data packets, water, electrical current, supply chains) through capacity-constrained directed links from a source to a sink.
Flow Network and Valid Flow
A flow network is a directed graph with a nonnegative capacity for every edge (and if ), a distinguished source , and a distinguished sink .
A flow is a real-valued function satisfying:
- Capacity Constraint: for all .
- Flow Conservation: For every intermediate vertex , total incoming flow equals total outgoing flow:
The value of flow is the net flow leaving the source:
Residual Networks, Augmenting Paths, and Cuts
- Residual Capacity: Given flow , the residual capacity is the additional flow that can be pushed from to (either along unused forward capacity or by canceling existing backward flow):
- Residual Network : Contains all edges with .
- Augmenting Path: Any simple path from to in . Its bottleneck capacity is .
- - Cut : A partition of into and such that and . Its capacity is . For any flow and any - cut , .
Max-Flow Min-Cut Theorem (Ford–Fulkerson)
If is a flow in a flow network with source and sink , then the following three conditions are equivalent:
- is a maximum flow in .
- The residual network contains no augmenting path from to .
- for some - cut of (specifically, taking to be the set of vertices reachable from in ).
3.2 Maximum flow algorithms
Several classic algorithms find a maximum flow by iteratively pushing flow along augmenting paths or maintaining preflows.
- Ford–Fulkerson Method: Repeatedly finds any augmenting path in and augments flow by until no path exists.
- If capacities are integers bounded by , each augmentation increases flow by at least , giving running time .
- Limitation: Pseudo-polynomial; with large capacities (or irrational capacities), an unfortunate path choice can perform steps or fail to terminate.
- Edmonds–Karp Algorithm: Specializes Ford–Fulkerson by always selecting a shortest augmenting path (fewest edges) using Breadth-First Search (BFS) in .
- The shortest-path distance never decreases, and each edge can become critical at most times, bounding total augmentations by and total time by (strongly polynomial).
- Dinic's Algorithm: Builds a level graph via BFS (retaining only edges with ) and finds a blocking flow using DFS until no - path remains in .
- Runs in in general graphs and on unit-capacity networks.
- Push–Relabel (Preflow–Push) Algorithm: Maintains a preflow (allowing excess flow at intermediate vertices) and integer height labels (, ). Excess is pushed downhill along admissible edges () or a vertex is relabeled (). Runs in generically or with FIFO/highest-label selection.
| Algorithm | Path / Flow Strategy | Worst-Case Time | Strongly Polynomial? |
|---|---|---|---|
| Ford–Fulkerson | Arbitrary augmenting path | (integer caps) | No (pseudo-polynomial) |
| Edmonds–Karp | Shortest augmenting path via BFS | Yes | |
| Dinic's Algorithm | Level graph + DFS blocking flow | Yes | |
| Push–Relabel | Local preflow push and height relabel | (or ) | Yes |
1
Consider a flow network with vertices and directed edges with capacities: , , , , and . Apply the Edmonds–Karp algorithm (BFS shortest augmenting paths, breaking ties alphabetically) to find the maximum flow from to , and exhibit a matching minimum - cut.
First BFS augmenting path: Shortest - paths have edges: and . Alphabetical tie-breaking selects .
- Bottleneck capacity: .
- Update flows: , . Total flow .
- Edge is saturated (); residual .
Second BFS augmenting path: In , the remaining -edge path is .
- Bottleneck capacity: .
- Update flows: , . Total flow .
- Edge is saturated (); residual .
Third BFS augmenting path and termination: In , BFS from reaches (residual ), then via (capacity ), then via (residual ): .
- Bottleneck capacity: .
- Update flows: , , . Total flow .
- Now both and are saturated. Vertices reachable from in are , leaving .
- Cut capacity: .
The maximum flow is (), certified by the minimum cut of capacity .
3.3 Bipartite matching
A matching in an undirected graph is a subset of edges such that no two edges in share an endpoint. In a bipartite graph (where every edge connects to ), a maximum bipartite matching maximizes .
Reduction to Maximum Flow
To solve maximum bipartite matching via max flow:
- Create a super-source and super-sink .
- Add directed edges for every , for every (), and for every .
- Assign capacity to every edge.
By the Integrality Theorem of network flows, because all capacities are , Edmonds–Karp or Ford–Fulkerson produces an integral flow , and is a maximum matching of size .
Hall's Marriage Theorem and König's Theorem
Let be a bipartite graph:
- Hall's Marriage Theorem: contains a matching that covers every vertex in (an -saturating matching) if and only if for every subset , its neighborhood satisfies:
- König's Theorem: The size of a maximum matching equals the size of a minimum vertex cover in any bipartite graph.
- Hopcroft–Karp Algorithm: Finds a maximal set of vertex-disjoint shortest augmenting paths simultaneously in each BFS + DFS phase (analogous to Dinic's algorithm on unit networks), achieving time.
3.4 Graph coloring
Proper Coloring and Chromatic Number
A proper -coloring of an undirected graph assigns one color to each vertex such that for every edge . The chromatic number is the minimum for which admits a proper -coloring.
Bounds, Theorems, and Algorithms
- Bipartite Characterization: if and only if is bipartite (contains no odd cycles).
- Greedy Upper Bound: Coloring vertices in any order using the smallest color not used by an already-colored neighbor requires at most colors, where is the maximum vertex degree.
- Brooks' Theorem: For any connected graph that is neither a complete graph nor an odd cycle , .
- Four Color Theorem: Every planar graph satisfies .
- Complexity: Testing takes time (BFS/DFS); testing for is NP-complete.
- Heuristics:
- Welsh–Powell Algorithm: Sort vertices in descending order of degree; assign each new color greedily to as many uncolored non-adjacent vertices as possible.
- DSATUR (Degree of Saturation): Repeatedly pick the uncolored vertex with the largest number of distinct colors among its neighbors (breaking ties by highest degree).
- Applications: Compiler register allocation (interference graphs), exam/timetabling scheduling, and wireless frequency assignment.
2
Apply the Welsh–Powell greedy coloring algorithm to the -vertex graph with edges: . Determine the vertex ordering by degree, the resulting color classes, and verify whether the coloring is optimal.
Compute vertex degrees and sort descending:
- (neighbors )
- (neighbors )
- (neighbors )
- (neighbors )
- (neighbors ) — wait: also connects to , so ().
- (neighbors ).
Sorted order (tie-breaking alphabetically): .
Assign colors greedily in Welsh–Powell order:
- Color 1: Pick . Scan remaining vertices for non-neighbors of : are all adjacent to ; is not adjacent to . Color class 1 .
- Color 2: Pick first uncolored vertex . Non-neighbors of among remaining : and touch , while is not adjacent to . Color class 2 .
- Color 3: Pick first uncolored vertex . Remaining uncolored vertex is not adjacent to . Color class 3 .
Verify optimality: The vertices form a triangle (), so . Since Welsh–Powell produced a valid -coloring, and the coloring is optimal.
Welsh–Powell order: . The graph is colored with colors—, , —which is optimal because forms a clique ().
3.5 PageRank algorithm
PageRank (Brin & Page, 1998) ranks nodes in a directed link graph (such as the World Wide Web) by modeling a random surfer who follows outgoing links uniformly at random and occasionally jumps ("teleports") to a random page.
Google Matrix and PageRank Equation
Let a directed graph have pages, where page has out-degree . Define the column-stochastic transition matrix by:
With damping factor (typically ), the Google matrix is:
and the PageRank vector () is the unique stationary eigenvector satisfying .
Why Teleportation and Power Iteration Work
- Spider Traps and Dead Ends: Without dangling-node handling, dead ends leak probability mass; without teleportation (), strongly connected sink components (spider traps) absorb all rank. Adding makes strictly positive, irreducible, and aperiodic.
- Convergence via Power Iteration: Starting from , iterate:
By the Perron–Frobenius theorem, power iteration converges geometrically at rate toward .
3
Consider a -page web graph with directed links , , , and . Using damping factor and initial uniform vector , perform one iteration of PageRank power iteration to compute .
Determine out-degrees and teleport baseline: , , (no dangling nodes). The teleport term is .
Compute each component of :
Check conservation of probability: .
After one iteration, , with page already holding the highest rank because it receives links from both and .
3.6 Community detection algorithm
Community detection partitions a complex network (social, biological, citation, or communication graph) into clusters (communities) with dense internal edges and sparse external edges between clusters.
Newman–Girvan Modularity Q
Given an undirected graph with adjacency matrix , edges, and vertex degrees , the modularity of a partition into communities measures the fraction of within-community edges minus the expected fraction in a random configuration model preserving node degrees:
where is the number of edges inside community and is the sum of degrees in community . Values typically indicate strong community structure.
Key Community Detection Algorithms
- Girvan–Newman Algorithm (Divisive Hierarchical):
- Computes edge betweenness centrality (fraction of all-pairs shortest paths traversing each edge).
- Iteratively removes the edge with the highest betweenness (bridge edges connecting communities) and recomputes betweenness until communities disconnect, selecting the dendrogram cut maximizing .
- Complexity: on sparse graphs (too slow for millions of nodes, accurate on small/medium networks).
- Louvain Algorithm (Agglomerative Greedy Modularity):
- Phase 1 (Local Moving): Starts with each node in its own community; repeatedly moves each node to the neighbor community giving the maximum modularity gain until a local maximum is reached.
- Phase 2 (Network Aggregation): Collapses each community into a single super-node (summing edge weights into self-loops and inter-community edges) and repeats Phase 1.
- Complexity: Empirically near-linear in practice, scaling to networks with millions of vertices.
Exercises
Practice Exercises — Advanced Graph Algorithms
State the Max-Flow Min-Cut Theorem and explain why Edmonds–Karp improves over generic Ford–Fulkerson. In a flow network with vertices and capacities , , , , and , find the maximum flow and identify a minimum - cut.
Max-Flow Min-Cut Theorem and Edmonds–Karp improvement: The theorem states that maximum flow value equals minimum - cut capacity, occurring precisely when the residual network has no augmenting - path. Generic Ford–Fulkerson runs in and can take exponentially many iterations if large-capacity paths alternate across small bottleneck edges; Edmonds–Karp always picks a shortest augmenting path via BFS, guaranteeing strongly polynomial time.
Run Edmonds–Karp on the network:
- Path : pushes (saturates ; residual ).
- Path : pushes (saturates ; residual ).
- Path : pushes (saturates , , and ).
Total flow . In , only is reachable from (since and are both saturated), giving cut with capacity (also has capacity ).
The maximum flow is (), verified by minimum cut of capacity .
Explain how maximum bipartite matching is reduced to maximum flow. Given bipartite parts and with edges , find a maximum matching and check whether Hall's condition holds for all subsets .
Reduction to max flow: Add source with unit-capacity edges for each , orient every bipartite edge with capacity , and add unit-capacity edges for each . Because capacities are integers, max flow gives an integral flow whose saturated edges form a maximum matching.
Find maximum matching and verify Hall's condition:
- Check Hall's condition :
- Singletons: (size ), (size ), (size ).
- Pairs: ; ; .
- Full set: .
- Hall's condition holds, so a perfect matching of size exists: .
By unit-capacity max-flow reduction and Hall's Theorem ( holds for all ), the maximum matching has size : .
State Brooks' Theorem and the greedy coloring upper bound . Give two graph families where , and explain how graph coloring models compiler register allocation.
Bounds and Brooks' Theorem: Greedy vertex coloring in any order uses at most colors because any vertex has at most neighbors, leaving at least one of colors unused. Brooks' Theorem states that for any connected graph , unless is a complete graph () or an odd cycle ().
Compiler register allocation: Construct an interference graph whose vertices are program variables (live ranges) and where an edge connects two variables if they are simultaneously live at some program point. Assigning CPU registers without conflict corresponds directly to finding a proper -coloring with physical registers (spilling variables to memory if ).
Greedy coloring gives ; Brooks' Theorem tightens this to for all connected graphs except complete graphs and odd cycles . In compilers, register allocation reduces to -coloring the variable live-range interference graph.
Explain the roles of damping factor and dangling nodes in the PageRank Google matrix . In a -page graph where page receives a single incoming link from page (which has out-degree ), page is a dangling node (out-degree , whose rank is redistributed uniformly across all pages in ), and all pages start with rank , compute after one iteration with .
Role of damping factor and dangling nodes: A dangling node has out-degree and would leak rank probability mass unless its column in is replaced by . The damping factor (typically ) adds a teleportation probability to every page, preventing spider traps from absorbing all rank and guaranteeing irreducibility and convergence of power iteration.
Compute : With dangling-node redistribution in , page (rank ) contributes to every page via , and page contributes to page :
Dangling-node replacement prevents rank leakage, while teleportation avoids spider traps and ensures unique convergence. With uniform dangling redistribution and , .
Compare the Girvan–Newman and Louvain community detection algorithms. Consider a -vertex graph consisting of two triangles and joined by a single bridge edge . Compute the modularity of the two-community partition , , and explain which edge Girvan–Newman removes first.
Compare Girvan–Newman and Louvain:
- Girvan–Newman is a divisive algorithm that repeatedly removes the edge of highest betweenness centrality ( on sparse graphs).
- Louvain is an agglomerative greedy modularity-maximization algorithm alternating local node moves and graph coarsening, running in near-linear time on large networks.
Compute modularity and identify first removed edge: Total edges , so . Vertex degrees are and .
- For : internal edges, degree sum .
- For : internal edges, degree sum .
Every shortest path between and ( pairs, counting unordered pairs) must cross bridge , giving the highest edge betweenness; Girvan–Newman removes first.
Girvan–Newman is divisive via edge betweenness (), whereas Louvain greedily maximizes modularity bottom-up (). For the two-triangle barbell graph, , and Girvan–Newman removes bridge first.