Algorithms and Time Complexity Analysis

Question 1: Stable Matching

Algorithm (Levitin Style)

**ALGORITHM** *GaleShapley*$(M, W)$
//Implements the Gale-Shapley algorithm for the Stable Marriage Problem
//Input: A set of $n$ men $M$, a set of $n$ women $W$, and their respective preference lists
//Output: A stable matching between $M$ and $W$
Initialize all men and women to free
**while** there exists a free man $m$ who has unproposed women on his list **do**
    $w \leftarrow$ the highest-ranked woman on $m$'s list to whom $m$ has not yet proposed
    **if** $w$ is free **then**
        assign $m$ and $w$ to be engaged to each other
    **else if** $w$ prefers $m$ to her current partner $m'$ **then**
        assign $m$ and $w$ to be engaged to each other
        change $m'$ to free
    **else**
        // $w$ rejects $m$, $m$ remains free
**return** the set of engagements

Time Complexity Derivation

The algorithm relies on a while loop that continues as long as there is a free man who hasn't exhausted his proposal list. In the worst-case scenario, every man might propose to every woman.

Since there are $n$ men, and each man can propose to a maximum of $n$ women, the maximum total number of proposals across the algorithm is $n \times n = n^2$.

In each iteration, finding the next woman to propose to takes $O(1)$ time. Determining if a woman prefers the new proposer over her current partner can also be executed in $O(1)$ time by precomputing a reverse preference array (ranking matrix) for the women.

Therefore, the overall worst-case time complexity is $O(n^2)$.

Question 2: Maximum Bipartite Matching

Algorithm (Levitin Style)

**ALGORITHM** *MaximumBipartiteMatching*$(G)$
//Finds a maximum matching in a bipartite graph by iterative improvement
//Input: A bipartite graph $G = (V, U, E)$
//Output: A maximum matching $M$
$M \leftarrow$ empty set
**while** there exists an augmenting path $P$ with respect to $M$ **do**
    $M \leftarrow M \oplus E(P)$  // Augment the matching along path P by flipping edge statuses
**return** $M$

Time Complexity Derivation

The algorithm iteratively searches for an augmenting path. We commonly use Depth-First Search (DFS) or Breadth-First Search (BFS) to find such paths (e.g., Kuhn's Algorithm).

Finding a single augmenting path explores vertices and edges up to the size of the graph, taking $O(|V| + |E|)$ time.

Each time an augmenting path is found, the total size of the matching $M$ increases by exactly 1.

Because a matching cannot exceed the total number of vertices on the smaller side of the bipartite graph, the augmentation process will occur at most $|V|$ times.

Therefore, iterating at most $|V|$ times with each step taking $O(|E|)$ time gives a total time complexity of $O(|V| \cdot |E|)$.

Question 3: Maximum Network Flow

Algorithm (Levitin Style)

**ALGORITHM** *FordFulkerson*$(G, s, t)$
//Implements the Ford-Fulkerson method for the maximum network flow problem
//Input: A network $G = (V, E)$ with capacities $c$, source $s$, and sink $t$
//Output: Maximum flow $f$ from $s$ to $t$
**for** each edge $(u, v)$ in $E$ **do**
    $f(u, v) \leftarrow 0$
**while** there exists an augmenting path $P$ from $s$ to $t$ in the residual network $G_f$ **do**
    $c_p \leftarrow \min \{ c_f(u, v) : (u, v) \text{ is in } P \}$
    **for** each edge $(u, v)$ in $P$ **do**
        **if** $(u, v)$ is a forward edge **then**
            $f(u, v) \leftarrow f(u, v) + c_p$
        **else**
            $f(u, v) \leftarrow f(u, v) - c_p$
**return** $f$

Time Complexity Derivation

The efficiency of the Ford-Fulkerson algorithm depends heavily on the maximum flow value, let's denote it as $F$.

In the absolute worst case (particularly with poorly chosen augmenting paths or irrational capacities), each path might only increase the total flow by a bottleneck capacity of 1 unit.

Finding an augmenting path in the residual graph using DFS or BFS takes $O(|V| + |E|) \approx O(|E|)$ time.

Since the flow increases by at least 1 unit per iteration, the while loop runs at most $F$ times.

Multiplying the number of iterations by the work done per iteration gives a time complexity of $O(|E| \cdot F)$.