Graph & Optimization — Ultra‑Dense Exam Notes (CLRS 4e)

Disjoint Sets (19.1)

• ADT. MAKE-SET(x), FIND-SET(x) (return rep), UNION(x,y) (merge by reps).
• Forest impl. Parent pointers; each set as a rooted tree.
• Heuristics. Union-by-rank/size (attach shorter to taller) + Path compression on FIND-SET.
• Complexity. Any sequence of \(m\) ops on \(n\) elements: \(O(m\,\alpha(n))\), where \(\alpha\) is inverse Ackermann (practically <= 4).
• Use cases. Kruskal’s MST; connectivity queries; offline dynamic connectivity; checking cycle creation.
• Proof sketch. Tarjan’s analysis with rank invariant: rank nondecreasing; #nodes of rank \(r\) ≤ \(n/2^r\); compression charges to ranks ⇒ \(\alpha(n)\).

Elementary Graph Algorithms (20.1–20.5)

• Representations. List: \(O(V+E)\) space; Matrix: \(O(V^2)\). Iteration cost: neighbors \(O(\deg v)\) vs \(O(V)\).
• BFS. Queue; discovers layers; computes shortest paths for unit-weight graphs. Time \(O(V+E)\).
  • Invariant. When a vertex \(u\) is dequeued, \(d[u]\) is final shortest distance.
  • Tree edges. to newly discovered whites; gray/black logic prevents re-enqueue.
• DFS. Stack/recursion; timestamps \(d[u], f[u]\); classifies directed edges: tree, back (to ancestor), forward (to descendant), cross (other). Time \(O(V+E)\).
• Topological sort. Valid iff DAG; order = decreasing \(f[u]\) (postorder).
• SCCs. Kosaraju: DFS on \(G\) to get stack by finish times; DFS on \(G^T\) popping order. Tarjan: one pass with lowlink; stack membership.
• Connectivity/Bipartiteness. BFS layers parity; odd cycle iff non-bipartite.

Minimum Spanning Trees (21.1–21.2)

• Goal. Connect all vertices minimizing total edge weight in connected, undirected, weighted graph.
• Cut Property. For any cut, the minimum-weight edge crossing it is safe (belongs to some MST).
• Cycle Property. For any cycle, the maximum-weight edge on that cycle is not in any MST.
• Uniqueness. If every cut has a unique light edge ⇒ unique MST. Distinct weights suffice (but not necessary).
• Kruskal. Sort edges ↑ weight; add if endpoints in different DSU sets. \(O(E\log E)\). Proof: safe edges via cut property.
• Prim. Grow a tree from root; maintain crossing edges in PQ.
  • Binary heap: \(O(E\log V)\); Fibonacci heap: \(O(E+V\log V)\).
  • Dense graphs: adjacency matrix + array gives \(O(V^2)\).
• Pitfalls. Graph must be connected (else compute MSF per component). Negative weights okay.

Single‑Source Shortest Paths (22.1–22.4)

• Relaxation. If \(d[v] > d[u]+w(u,v)\): set \(d[v]=d[u]+w(u,v)\), \(\pi[v]=u\). Distances monotonically decrease.
• BFS (unweighted). Unit weights ⇒ breadth layers give shortest paths in \(O(V+E)\).
• DAG‑SSSP. Topological order; relax edges once. \(O(V+E)\). Works with negative edges (no cycles).
• Bellman–Ford. Repeat \(V-1\) full relaxations; detect negative cycles if any edge relaxes in \(V\)-th pass. \(O(VE)\).
• Dijkstra. Nonnegative weights; PQ extract‑min settles vertex with final distance.
  • Binary heap: \(O(E\log V)\); Fibonacci: \(O(E+V\log V)\); array: \(O(V^2)\) (dense).
  • Counterexample. Fails with negative edges (even if no neg cycles).
• Difference constraints. Constraints \(x_v-x_u \le c_{uv}\). Build edges \(u\to v\) with weight \(c_{uv}\). Feasible iff no negative cycle; potentials from BF give one feasible solution.

All‑Pairs Shortest Paths (22.5; 23.1–23.2)

• Floyd–Warshall. DP over allowed intermediates \(k\): \(D^{(k)}[i,j]=\min\{D^{(k-1)}[i,j],\,D^{(k-1)}[i,k]+D^{(k-1)}[k,j]\}\). Runtime \(O(V^3)\), space \(O(V^2)\).
  • Negative cycle detection: some \(D[i,i] < 0\) at end.
• Johnson’s algorithm. Add super‑source \(s\) to all \(v\); run BF to compute \(h(v)=\delta(s,v)\); reweight \(w'(u,v)=w(u,v)+h(u)-h(v)\ge 0\). Then Dijkstra from each source; recover original distances \(d(u,v)=d'(u,v)-h(u)+h(v)\).
  • Runtime \(O(VE + V E\log V)\) with heaps; handles negative edges, no neg cycles.

Maximum Flow (24.1–24.3)

• Flow network. Directed graph with capacities \(c(u,v)\); flow \(f\) satisfies capacity and conservation.
• Residual graph. \(c_f(u,v)=c(u,v)-f(u,v)\) (forward) and \(c_f(v,u)=f(u,v)\) (backward).
• Ford–Fulkerson. While there exists augmenting path \(P\) in residual, augment by \(\min\) residual on \(P\).
• Edmonds–Karp. Choose shortest (in edges) augmenting path via BFS ⇒ each edge becomes critical \(O(V)\) times ⇒ \(O(VE^2)\).
• Max‑Flow Min‑Cut Theorem. Value of max flow equals capacity of min \(s\)–\(t\) cut. At termination, vertices reachable from \(s\) in residual form the min‑cut side \(S\).
• Common reductions. Edge/vertex disjoint paths; bipartite matching (convert to flow); project selection; circulation with demands.
• Pitfalls. Irrational capacities + naive augmenting choices can cycle; EK avoids by BFS choice.

Linear Programming (29.1–29.3)

• Standard form. \(\max c^\top x\) s.t. \(Ax \le b,\ x\ge 0\). Convert \(=\) or \(\ge\) via slack/surplus and sign splits.
• Geometry. Feasible region is a polyhedron; optima occur at vertices (basic feasible solutions, BFSs).
• Duality. Dual of standard max: \(\min\{b^\top y: A^\top y \ge c,\ y\ge0\}\). Strong duality holds; weak duality always.
• Complementary slackness. For primal \(x^*\), dual \(y^*\):
  • If \(x_j^*>0\) then \((A^\top y^*)_j=c_j\).
  • If \(y_i^*>0\) then \((Ax^*)_i=b_i\).
• Modeling motifs. Assignment & bipartite matching as LPs (totally unimodular ⇒ integral BFS); min‑cut dual to max‑flow in certain formulations.
• Algorithms. Simplex (often fast, worst‑case exponential); Ellipsoid/Interior‑Point (polynomial time).

String Matching (32.1–32.2)

• Naïve. Slide pattern \(P\) over text \(T\); worst \(O((n-m+1)m)\).
• Rabin–Karp. Rolling hash with base \(d\) and modulus \(q\): \(H_{i+1}=(d(H_i - T_i d^{m-1}) + T_{i+m}) \bmod q\). Verify on hash match. Expected \(O(n+m)\); worst \(O(nm)\) (adversarial collisions).
• Use cases. Multiple pattern search with sum of \(m\) over patterns; plagiarism detection; fast filters.

NP‑Completeness (34.1–34.5)

• Classes. \(P\): solvable in poly‑time. \(NP\): verifiable in poly‑time. \(coNP\): complements of \(NP\).
• Reductions. \(A \le_p B\): poly‑time map \(f\) with \(x\in A \iff f(x)\in B\). If \(A\le_p B\) and \(B\in P\) ⇒ \(A\in P\).
• NP‑hard / NP‑complete. \(L\) NP‑hard if every \(L'\in NP\) reduces to \(L\). NP‑complete if NP‑hard and \(L\in NP\).
• Canonical NP‑complete problems. SAT → 3SAT → CLIQUE / Vertex‑Cover / Independent‑Set; Hamiltonian‑Cycle; Subset‑Sum; Partition; 3‑Coloring.
• Proof recipe (exam routine).
  1. Choose known NP‑complete problem \(A\).
  2. Give poly‑time mapping \(f\) to your target \(B\).
  3. Prove correctness: \(x\in A \iff f(x)\in B\).
  4. Conclude \(B\) NP‑complete (and \(B\in NP\)).
• Implications. If any NP‑complete problem is in \(P\), then \(P=NP\). Otherwise unknown.

Complexity & Key Facts (Quick Reference)

Exam Patterns & Proof Sketches

• MST uniqueness. Show every cut has unique light edge ⇒ that edge must be in every MST ⇒ uniqueness.
• Dijkstra correctness. Loop invariant: extracted \(u\) has \(d[u]=\delta(s,u)\); proof by contradiction using nonnegativity.
• EK runtime. Distances in residual (in edge count) to \(t\) are nondecreasing; each edge saturates \(O(V)\) times.
• FW recurrence. “Allow intermediates among \(\{1..k\}\)”: either route avoids \(k\) or goes \(i\to k\to j\).
• LP CS conditions. Use to certify optimality: provide primal/dual feasible pair meeting CS.
• NP‑C proof. Always check membership in \(NP\) + reduction direction is from known NP‑C to your problem.