How Hungarian Algorithm Bipartite Matching Works: Deep Dive with Code

1. Introduction and Core Concepts

The hungarian algorithm bipartite matching is one of the most elegant and practically important algorithms in combinatorial optimization. It solves the assignment problem: given two disjoint sets of equal size and a cost for pairing each element from the first set with each element from the second, find the perfect matching with minimum total cost. While the name suggests a narrow use case, the underlying principle powers everything from job scheduling to resource allocation in modern distributed systems.

To understand why this matters, consider the formal definition of a bipartite graph G = (U, V, E) where vertices are divided into two partitions U and V such that every edge connects a vertex in U to a vertex in V. A matching is a set of edges without common vertices. A perfect matching covers every vertex. When each edge (u, v) has a weight or cost c(u, v), the assignment problem asks for the perfect matching that minimizes the sum of selected edge costs. This is not just any matching problem — it is a weighted, balanced, one-to-one assignment.

The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, was developed by Harold Kuhn in 1955 based on earlier work by Hungarian mathematicians Dénes König and Jenő Egerváry. Kuhn's original O(n⁴) algorithm was later improved to O(n³) by Jack Edmonds and Richard Karp. Its significance lies in proving that the assignment problem is solvable in polynomial time, unlike many combinatorial problems that are NP-hard. A naive brute-force search would need to evaluate n! permutations, which becomes intractable even for n=15.

Why Not Just Use Greedy Matching?

A greedy approach that repeatedly picks the cheapest available edge fails dramatically for assignment problems. A locally optimal choice can block globally optimal pairings, leading to arbitrarily bad total costs. The Hungarian algorithm avoids this trap by maintaining feasible dual variables (potentials) and systematically improving the matching through augmenting paths, guaranteeing global optimality without exhaustive search.

Key terminology you must know before diving deeper includes: cost matrix (an n x n matrix where entry C[i][j] is the cost of assigning worker i to job j), feasible labeling (potentials u and v such that u[i] + v[j] ≤ C[i][j] for all i,j), equality subgraph (the subgraph containing only tight edges where u[i] + v[j] = C[i][j]), and augmenting path (an alternating path that increases matching size by one). The algorithm's genius is in how it manipulates these concepts to converge on an optimal solution.

2. How It Works

At its core, the Hungarian algorithm is a primal-dual algorithm for the linear programming formulation of the assignment problem. The primal problem is to minimize sum of C[i][j] * x[i][j] subject to each row and column being assigned exactly once. The dual problem introduces potentials u[i] for rows and v[j] for columns to maximize sum(u[i]) + sum(v[j]) subject to u[i] + v[j] ≤ C[i][j]. By strong duality, when a feasible matching uses only tight edges, it is optimal for both.

The algorithm maintains a feasible labeling and a matching M within the equality subgraph. Initially, it sets u[i] = min_j C[i][j] and v[j] = 0, which is trivially feasible, and starts with an empty matching. It then iteratively tries to find a perfect matching in the equality subgraph. If it succeeds, that matching is optimal. If not, there exists an unmatched row vertex that cannot be augmented within the current equality subgraph, and the labeling must be adjusted to bring new edges into the equality subgraph.

The adjustment step is the most subtle part. Let S be the set of row vertices reachable from an unmatched row via alternating paths in the equality subgraph, and T be the set of column vertices reachable similarly. Compute delta = min{ C[i][j] - u[i] - v[j] | i in S, j not in T }. This delta is the smallest slack among edges crossing from S to outside T. We then update potentials: u[i] -= delta for i in S, v[j] += delta for j in T. This preserves feasibility, keeps all previous tight edges tight, and adds at least one new tight edge, strictly expanding the search space.

The Augmenting Path Search

Finding augmenting paths is performed similarly to bipartite matching via BFS or DFS, but restricted to the equality subgraph. For each unmatched row, we run a search to find an augmenting path to an unmatched column. If found, we flip the matched/unmatched status along the path, increasing matching size by one. If not found, we use the S and T sets from the failed search to compute delta and update potentials, then retry the search without resetting. This ensures each row is matched in at most n phases.

Intuition: Row and Column Reduction

An alternative intuitive view taught in operations research frames the algorithm as row reduction, column reduction, covering zeros, and shifting. Subtracting row minima and column minima creates at least one zero per row and column. Covering all zeros with a minimum number of lines tests for optimality: if n lines are needed, an assignment of zeros exists. Otherwise, we shift uncovered costs by the minimum uncovered value. This matrix view is mathematically equivalent to the primal-dual potential updates but is often easier to visualize on paper.

3. Implementation

Implementing the Hungarian algorithm correctly requires careful handling of potentials, matching arrays, and slack values. The O(n³) implementation below is the standard competitive programming version inspired by emaxx.ru, which efficiently handles both square and rectangular matrices. It uses 1-indexed auxiliary arrays for cleaner logic and avoids explicit graph construction.

import math

def hungarian(cost):
    """
    Hungarian algorithm for minimum assignment.
    cost: n x m matrix (n <= m). For square, n == m.
    Returns (min_cost, assignment) where assignment[i] = column for row i
    """
    n = len(cost)
    m = len(cost[0])
    # potentials for rows (u) and columns (v)
    u = [0] * (n + 1)
    v = [0] * (m + 1)
    # p[j] = row assigned to column j, way[j] = previous column in augmenting path
    p = [0] * (m + 1)
    way = [0] * (m + 1)

    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [math.inf] * (m + 1)
        used = [False] * (m + 1)
        while True:
            used[j0] = True
            i0 = p[j0]  # current row to consider
            delta = math.inf
            j1 = 0
            for j in range(1, m + 1):
                if not used[j]:
                    cur = cost[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j
            # update potentials
            for j in range(0, m + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        # augmenting: flip path
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break

    # build answer: assignment[row] = col
    assignment = [-1] * n
    for j in range(1, m + 1):
        if p[j] != 0:
            assignment[p[j] - 1] = j - 1
    min_cost = -v[0]  # or sum(cost[i][assignment[i]] for i in range(n))
    return min_cost, assignment

This implementation implicitly maintains the equality subgraph through the slack array minv. The variable delta corresponds exactly to the potential adjustment described in the theory. The inner loop runs in O(m) and the outer loop runs n times, with each augmentation taking O(n*m), yielding O(n² * m) which is O(n³) for square matrices. Note the escaping of < and > is required for HTML safety but represents standard Python comparisons.

# Example usage: assigning 3 workers to 3 jobs
cost_matrix = [
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1]
]

min_cost, assign = hungarian(cost_matrix)
print(f"Minimum cost: {min_cost}")  # Expected: 9
print(f"Assignment: {assign}")      # e.g., [1, 0, 2] means worker0->job1, etc.

# Verify cost
total = sum(cost_matrix[i][assign[i]] for i in range(len(cost_matrix)))
print(f"Verified total: {total}")

# For maximum weight matching, negate or transform costs
def hungarian_max(weight):
    max_val = max(max(row) for row in weight)
    # Convert to minimization: cost = max_val - weight
    cost = [[max_val - w for w in row] for row in weight]
    min_cost, assign = hungarian(cost)
    max_weight = sum(weight[i][assign[i]] for i in range(len(weight)))
    return max_weight, assign

weights = [[10, 5, 8], [7, 8, 5], [6, 9, 4]]
print(hungarian_max(weights))

For rectangular problems where n < m (more jobs than workers), the same code works directly — it finds the minimum cost matching that assigns every row to a distinct column, leaving m-n columns unmatched. For n > m, simply transpose the matrix or pad with dummy zero-cost columns. When you need maximum weight bipartite matching instead of minimum cost, transform the matrix as shown above or multiply costs by -1 if your implementation supports negative costs.

from scipy.optimize import linear_sum_assignment
import numpy as np

# Production-ready alternative using SciPy (wraps LAPJV algorithm)
cost = np.array([[9, 2, 7], [6, 4, 3], [5, 8, 1]])
row_ind, col_ind = linear_sum_assignment(cost)
print(f"SciPy assignment: {list(zip(row_ind, col_ind))}")
print(f"Total cost: {cost[row_ind, col_ind].sum()}")

# Handling unbalanced and forbidden assignments
INF = 10**9
cost_unbalanced = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2],
    [7, 4, 6]
])  # 4 workers, 3 jobs - will assign 3 workers optimally
# Pad to square with zero-cost dummy jobs if all workers must be considered
# Or use linear_sum_assignment directly - it handles rectangular

# Forbidden assignment: set cost to large INF
cost_with_forbidden = np.array([
    [4, INF, 3],
    [2, 0, 5],
    [3, 2, 2]
])
row_ind, col_ind = linear_sum_assignment(cost_with_forbidden)
# Filter out INF assignments if needed
valid = [(r, c) for r, c in zip(row_ind, col_ind) if cost_with_forbidden[r, c] < INF]
print(f"Valid assignments avoiding forbidden: {valid}")

In production Python code, prefer scipy.optimize.linear_sum_assignment which implements the Jonker-Volgenant algorithm, a highly optimized variant of the Hungarian algorithm that is faster in practice and numerically stable. However, understanding the pure Python implementation is essential for interviews, custom constraints, and environments where SciPy is unavailable.

def hungarian_with_potentials_debug(cost):
    """Instrumented version to inspect dual variables u, v and slack."""
    n = len(cost)
    u = [0]*(n+1)
    v = [0]*(n+1)
    p = [0]*(n+1)
    way = [0]*(n+1)
    for i in range(1, n+1):
        p[0] = i
        j0 = 0
        minv = [float('inf')]*(n+1)
        used = [False]*(n+1)
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = float('inf')
            j1 = 0
            for j in range(1, n+1):
                if not used[j]:
                    cur = cost[i0-1][j-1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j
            for j in range(n+1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break
        # Debug: print potentials after each row matched
        print(f"After matching row {i}: u={u[1:]}, v={v[1:]}")
    return -v[0], p

cost = [[9, 2, 7],[6, 4, 3],[5, 8, 1]]
hungarian_with_potentials_debug(cost)
# Observe how u + v <= cost always holds (feasibility)
# and equality holds for matched edges

4. Step-by-Step Example

Let us walk through a concrete 3x3 example to make the abstract updates tangible. Consider three workers (A, B, C) and three jobs (1, 2, 3) with cost matrix:

C = [[9, 2, 7], [6, 4, 3], [5, 8, 1]] where rows are A, B, C and columns are 1, 2, 3. The optimal assignment is A->2 (2), B->1 (6), C->3 (1) for total cost 9. Let us see how the algorithm discovers it.

Initialization: u = [min row] = [2, 3, 1], v = [0,0,0]. The equality subgraph contains edges where C[i][j] == u[i]+v[j]. So row A has edge to col 2 (2==2+0), row B to col 3 (3==3+0), row C to col 3 (1==1+0). Note row C and B both want col 3.

Iteration 1 (Row A): BFS from A in equality subgraph reaches col 2 which is free, so we augment and match A-2. Matching = {A-2}. S={A}, T={2} after search.

Iteration 2 (Row B): Start from B. Equality edges from B go to col 3 (free). So B-3 is augmenting, match B-3. Matching = {A-2, B-3}.

Iteration 3 (Row C): Start from C. Equality edge C-3 leads to B (since B is matched to 3). From B, no other equality edges, so search stalls. S = {C, B}, T = {3}. Compute delta = min{ C[i][j] - u[i] - v[j] for i in S, j not in T } = min( C[C][1]-1-0=4, C[C][2]-1-0=7, C[B][1]-3-0=3, C[B][2]-3-0=1 ) = 1 (edge B-2). Update: u[C]+= -1? Wait update rule u[i]-=delta for i in S? In our code variant u increases for S. Equivalent shift: u[B]=4, u[C]=2, v[3]=-1. New equality edges: B-2 becomes tight (4 + -? Let's compute). Now re-run search from C: C-3 -> B -> 2 -> A. Since A is matched to 2, we reach A, from A no new edges, stall again. S={C,B,A}, T={3,2}. delta = min{ C[A][1]-2-0=7, C[A][3]-2-(-1)=6, C[B][1]-4-0=2, C[C][1]-2-0=3 } =2 (B-1). Update potentials again. Now B-1 becomes tight. Search: C-3 -> B ->1 (free!). Augmenting path is C-3-B-1. Flipping gives matching {A-2, B-1, C-3} with total 9, which is optimal. Potentials now satisfy u+v ≤ C with equality on matched edges.

Visualizing the Matrix Reduction Method

Using the classic textbook method on the same matrix: Step 1 subtract row minima (2,3,1) gives [[7,0,5],[3,1,0],[4,7,0]]. Subtract column minima (3,0,0) gives [[4,0,5],[0,1,0],[1,7,0]]. Cover zeros with minimum lines: we can cover with 2 lines (row2 and column2?), not 3, so not optimal. Minimum uncovered is 1. Subtract 1 from uncovered, add 1 to double-covered. New matrix [[5,1,5],[0,1,0],[0,6,0]]? Actually after proper shift we get optimal zeros allowing assignment at (A,2), (B,1), (C,3). This mirrors the potential updates.

The key takeaway from the walkthrough is that the algorithm never makes an irrevocable greedy choice. When C collides with B on job 3, it does not settle; it adjusts potentials to reveal alternative cheaper edges (B-2, then B-1) and reroutes the matching via augmenting paths. This backtracking via potentials is what guarantees optimality.

5. Complexity Analysis

Complexity analysis of the Hungarian algorithm is nuanced because several variants exist with different trade-offs. The original Kuhn version was O(n⁴), the Edmonds-Karp improvement achieves O(n³), and with Fibonacci heaps the theoretical bound can be pushed to O(n² log n + n*m) for sparse graphs, though the O(n³) implementation remains dominant for dense assignment matrices.

For a square n x n dense cost matrix, the O(n³) implementation runs in cubic time regardless of input distribution — there is no early exit for easy instances because potentials must be adjusted n times. For rectangular n x m matrices with n ≤ m, complexity is O(n² * m). Space complexity is O(n*m) to store the cost matrix plus O(n+m) auxiliary arrays, which is optimal since the input itself is O(n*m).

Best, average, and worst cases are identical in asymptotic terms for the dense implementation, but constant factors vary. If the initial equality subgraph already contains a perfect matching (e.g., costs are random and diverse), fewer potential updates are needed. In the worst case where many costs are equal, more augmentations and delta computations occur, though still bounded by O(n³).

For sparse bipartite graphs where m << n² (few allowed edges, many INF costs), specialized sparse Hungarian variants using Dijkstra with potentials achieve O(n (m + n log n)), which can be dramatically faster. However, they require adjacency lists and heap structures, increasing implementation complexity.

Memory access patterns matter in practice. The dense O(n³) algorithm is cache-friendly for n up to a few thousand, while SciPy's LAPJV variant uses additional bookkeeping to reduce constant factors by ~2-5x. For n > 5000, consider approximate algorithms or parallel implementations, as cubic scaling becomes prohibitive (n=10,000 implies ~1e12 operations).

6. Variations and Optimizations

The classic Hungarian algorithm assumes a square, balanced, minimization problem. Real-world problems rarely fit so neatly, so several variations have emerged. The most common is the rectangular assignment where the number of workers and jobs differ. This is solved by padding the cost matrix to square with dummy zeros or by using the unbalanced O(n² m) version directly, which is more efficient than padding.

Maximization vs minimization is trivially handled by transformation. To maximize weight, set cost' = maxWeight - weight or cost' = -weight. If the algorithm requires non-negative costs, use the first transformation. For stability with large weights, prefer negation and allow negative potentials, as subtracting maxWeight can cause overflow or loss of precision with floating costs.

Handling forbidden assignments (e.g., worker A cannot do job 3) is done by setting cost to INF (a very large number). However, naive INF can break potential updates if INF - u - v overflows. A robust approach checks for INF before computing slack and excludes those edges from delta calculation. Alternatively, model the problem as a sparse graph and simply omit forbidden edges.

Jonker-Volgenant and LAPJV

The Jonker-Volgenant (JV) algorithm is the most important optimization, used in SciPy. It improves the initialization via an augmenting row reduction and column reduction that greedily builds a partial matching, then uses Dijkstra-like shortest augmenting paths with potentials. In practice JV is 10-100x faster than naive Hungarian on random matrices, though it retains O(n³) worst-case.

Incremental and Online Variants

When assignments must be updated dynamically (e.g., new jobs arrive), recomputing from scratch is wasteful. Incremental Hungarian algorithms reuse previous potentials and matching, achieving O(n²) per update. For very large n, approximation algorithms like the auction algorithm (Bertsekas) provide epsilon-optimal solutions in O(n² log(nC)) and are highly parallelizable on GPUs, making them popular for computer vision tracking with n > 10k.

Other optimizations include: using 32-bit integers when costs are integral to improve cache and speed, Bitset representations for the equality subgraph to accelerate BFS, and early exit for k-best assignments where only top-k matchings are needed via successive shortest paths. For floating-point costs, ensure epsilon comparisons (cur < minv[j] - 1e-9) to avoid cycling due to precision errors.

7. Real-World Applications

Despite its theoretical origins, hungarian algorithm bipartite matching is embedded in countless production systems. Its ability to optimally pair two sets under cost constraints makes it a universal assignment primitive.

In web servers and cloud infrastructure, load balancers use assignment to map incoming requests to backend servers minimizing latency or maximizing throughput. Databases use it for join order optimization and replica assignment. Networks use it for channel assignment in wireless communications and for optimal routing in switch fabrics. The algorithm's deterministic optimality is crucial where suboptimal greedy placement would cause hotspots or SLA violations.

In computer vision and tracking, the Hungarian algorithm is the de facto standard for multi-object tracking (e.g., DeepSORT, SORT). At each video frame, detections are matched to existing tracks based on IoU or appearance distance; the Hungarian algorithm finds the globally optimal association, minimizing identity switches. Similarly, in natural language processing, it aligns words for evaluation metrics and in bioinformatics it aligns proteins.

Economics and operations research provide classic examples: assigning workers to jobs, taxis to riders, or kidney donors to recipients (with weights reflecting compatibility). Transportation companies solve the vehicle routing assignment daily, while airlines assign crews to flights under complex cost and regulatory constraints.

A concrete web-scale example: a content delivery network must assign 1,000 edge caches to 1,000 user clusters every minute based on real-time latency measurements. Running Hungarian O(n³) takes ~1e9 operations (~0.3 seconds in optimized C++), yielding optimal latency versus a greedy heuristic that might be 15-30% worse and cause regional overloads. For larger n, the system partitions geographically and runs Hungarian per region.

8. Comparison with Alternatives

Choosing the right bipartite matching algorithm depends on whether edges are weighted, whether you need perfect matching, graph density, and scale. The Hungarian algorithm is optimal for dense weighted assignment, but other algorithms dominate in different regimes.

For unweighted maximum cardinality matching (just maximize number of pairs, no costs), Hopcroft-Karp is far superior at O(E sqrt(V)). For weighted but sparse graphs where not all pairings are allowed, successive shortest augmenting path min-cost max-flow is more flexible. For very large dense problems where exact optimality is not critical, greedy or auction approximations trade 1-5% optimality for 10x speedup.

In practice, the decision tree is: If your graph is unweighted, use Hopcroft-Karp. If weighted and dense with n < 5000 and you need exact optimum, use Hungarian / LAPJV (SciPy). If weighted and sparse or you have capacities >1, use min-cost max-flow. If n > 10000 and you can tolerate 1% error, use auction or greedy with local search. Never use brute force beyond n=10 except for testing correctness of Hungarian implementations on small random matrices.

9. Common Mistakes and Best Practices

Even experienced engineers stumble on subtle pitfalls when implementing or applying the Hungarian algorithm. The most frequent mistake is forgetting that the algorithm minimizes cost. When the problem asks to maximize profit or similarity, failing to transform weights leads to the worst possible assignment. Always clarify objective direction and convert via max - weight or negation, and test on a 2x2 example where max and min differ.

Another critical error is mishandling rectangular matrices. Padding with zeros is correct only if dummy assignments should have zero cost; padding with large INF incorrectly forces unnecessary assignments. For n > m (more workers than jobs), you must transpose or explicitly allow unmatched rows. The O(n² m) implementation handles n ≤ m natively — ensure you pass the smaller dimension as rows to minimize complexity.

Numerical issues plague floating-point cost matrices. Using exact equality (cur == 0) to test tightness fails due to precision; use epsilon thresholds (abs(cur) < 1e-9). When costs are large (e.g., 1e9), delta updates can overflow 32-bit integers; use 64-bit (Python int is unbounded, but NumPy int32 is not). When using INF for forbidden edges, choose INF > sum of all feasible costs but < overflow threshold, e.g., 1e12 for costs up to 1e6.

Best Practices Checklist

• Validate input: ensure cost matrix is rectangular, no NaNs, and n > 0. For SciPy, convert to numpy array of dtype float or int.
• Normalize costs: if costs vary by orders of magnitude, scale to improve numerical stability. For integer costs, keep them integral to avoid floating errors.
• Test on small cases: compare Hungarian output to brute force for n=4 random matrices in unit tests to catch off-by-one errors in 1-indexed arrays.
• Profile before optimizing: for n < 500, pure Python Hungarian is fine; for n > 1000, switch to SciPy or C++ bindings. Do not prematurely implement sparse variants for dense problems.
• Handle multiple optimal solutions: Hungarian returns one optimum arbitrarily. If you need all optima or k-best assignments, use Murty's algorithm on top of Hungarian.
• Log potentials for debugging: when assignment looks wrong, print u, v and verify u[i] + v[j] ≤ cost[i][j] for all i,j and equality for matched edges.

Finally, remember that Hungarian finds a perfect matching. If your problem allows leaving vertices unmatched at a penalty, model it by adding dummy vertices with penalty costs rather than post-filtering the perfect matching, which would be suboptimal. This preserves the global optimality guarantee while respecting real-world flexibility.

10. Interview Questions

Interviewers love the Hungarian algorithm because it tests graph theory, optimization, and implementation skill. Expect both conceptual and coding questions.

Q1: Explain why the Hungarian algorithm guarantees optimality. What role do potentials play?

Answer: The algorithm maintains a feasible dual labeling u, v such that u[i] + v[j] ≤ C[i][j]. Any perfect matching M has cost at least sum(u)+sum(v) (weak duality). When the algorithm finds a perfect matching M* inside the equality subgraph (where u[i]+v[j]=C[i][j] for all edges in M*), its cost equals sum(u)+sum(v), so by strong duality it is optimal. Potentials are dual variables that certify optimality; delta updates preserve feasibility while expanding the equality subgraph until such a matching exists.

Q2: How would you adapt Hungarian to handle an unbalanced assignment where there are more workers than jobs?

Answer: Three options: (1) Transpose so n ≤ m and run rectangular Hungarian which finds min-cost matching covering all rows. (2) Pad the cost matrix to square with dummy columns of zero cost (or appropriate penalty), then run square Hungarian; dummy matches represent unmatched workers. (3) Model as min-cost max-flow with source to workers, workers to jobs, jobs to sink. The most efficient is (1) using O(n² m) implementation without explicit padding, ensuring the smaller side is iterated as rows.

Q3: What is the time complexity of Hungarian and how does it compare to brute force? When would you prefer min-cost max-flow?

Answer: Hungarian is O(n³) for n x n dense matrices, versus O(n! * n) for brute force enumerating permutations. For n=20, brute force is ~2e18 operations (infeasible) while Hungarian is 8000 operations. Prefer min-cost max-flow when the graph is sparse (E << n²), when capacities exceed 1 (e.g., a worker can take multiple jobs), or when you need to handle forbidden edges naturally without INF tricks. Min-cost flow with successive shortest paths and potentials runs in O(F * (E log V)) where F is flow value, better for sparse cases.

Q4: Walk through one iteration of the matrix covering method on a 3x3 example.

Answer: Use the earlier example [[9,2,7],[6,4,3],[5,8,1]]. Subtract row mins [2,3,1] → [[7,0,5],[3,1,0],[4,7,0]]. Subtract col mins [3,0,0] → [[4,0,5],[0,1,0],[1,7,0]]. Cover zeros with minimum lines: try to cover all zeros; you need 2 lines (e.g., row2 and column2), < n=3 so not optimal. Find min uncovered =1, subtract from uncovered cells and add to doubly covered cells → new matrix allows 3 lines covering zeros, indicating an optimal assignment exists at zero positions (A2, B1, C3). This demonstrates the potential shift in matrix form.

Q5: How do you handle maximum weight matching and forbidden assignments in code?

Answer: For maximum weight, transform costs: if Hungarian minimizes, set cost = maxWeight - weight or cost = -weight (if negatives allowed). Verify by checking that minimizing transformed cost maximizes original weight. For forbidden assignments, set cost to INF (e.g., 10**12) and ensure delta computation skips INF edges to avoid overflow, or use sparse representation omitting those edges. After solving, verify no INF edge was selected; if it was, the instance is infeasible (no perfect matching without forbidden edges). In SciPy, use a large INF and filter results where cost >= INF/2.

Preparing for these questions requires not just memorizing complexity but being able to code the O(n³) version from scratch, debug potential updates, and discuss trade-offs with alternatives. Practice implementing the 1-indexed version and testing against brute force on random 5x5 matrices to build confidence.