Agent Work: Homework6

Claude Haiku 4.5 · COMP 382: Reasoning about Algorithms

COMP 382: Reasoning about Algorithms

Homework 6

Total Points: 100 (Each problem is worth 20 points)

---

Problem 1: True or False [20 points]

Say whether the following claims are true or false. Justify each of your answers with either a proof or a counterexample.

Part (a)

Any flow graph G has a maximum flow that does not include a cycle in which each edge has positive flow.

Part (b)

If all edges in a graph have distinct capacities, there is a unique maximum flow.

Part (c)

If we multiply all edge capacities in a flow network by a positive number λ, then the minimum cut stays unchanged.

Part (d)

If we add a positive number λ to all edge capacities, then the minimum cut stays unchanged.

---

Problem 2: Flow Reduction [20 points]

You are given a flow network with unit-capacity edges: It consists of a directed graph G = (V, E), a source s ∈ V, and a sink t ∈ V; and capacity cₑ = 1 for every e ∈ E. You are also given a parameter k.

The goal is to delete k edges so as to reduce the maximum s-t flow in G by as much as possible. In other words, you should find a set of edges F ⊆ E so that |F| = k and the maximum s-t flow in G' = (V, E \ F) is as small as possible.

Give a polynomial-time algorithm (k cannot occur in the exponent of the complexity term) to solve this problem.

---

Problem 3: Node Capacities [20 points]

In a standard s-t Maximum Flow problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node. In this problem, we consider the variant of the MaxFlow problem with node capacities.

Let G = (V, E) be a directed graph, with source s ∈ V, sink t ∈ V, and a non-negative node capacity cᵥ for each node. Given a flow f in this graph, the flow through a node v is defined as f^in(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints f^in(v) ≤ cᵥ for all nodes.

Give a polynomial-time algorithm to find an s − t maximum flow in such a node-capacitated network.

---

Problem 4: Station Closing [20 points]

Suppose you are in charge of a rail network connecting a large number of towns. Recently, several cases of a contagious disease have been reported in a town A. Your goal is to close down certain railway stations to prevent the disease from spreading to your hometown B. No trains can pass through a closed station.

To minimize expense, you want to close down as few stations as possible. However, you cannot close the station A, as this would expose you to the disease, and you cannot close the station B, because then you couldn't visit your favorite pub.

Describe and analyze an efficient algorithm, based either on max-flow or min-cut, to find the minimum number of stations that must be closed to block all rail travel from A to B.

The rail network is represented by an undirected graph, with a vertex for each station and an edge for each rail connection between two stations. Two special vertices represent the stations in A and B.

---

Problem 5: Exam Scheduling [20 points]

Consider the following problem of scheduling exams at a university. The university offers n different classes. There are r different rooms on campus and t different time slots in which exams can be offered.

You are given two arrays E[1...n] and S[1...r], where:

E[i] is the number of students enrolled in the i-th class
S[j] is the number of seats in the j-th room

At most one final exam can be held in each room during each time slot. Class i can hold its final exam in room j only if E[i] < S[j].

Give an efficient max-flow or min-cut based algorithm to assign a room and a time slot to each class (or report correctly that no such assignment is possible).

State and briefly explain the complexity of your algorithm.

writeup.md206 B

markdown

# COMP382 Homework 6

## Student Responses

<!-- Write your solutions below. Add sections for each problem as needed. -->
<!-- Use proper mathematical notation where applicable. -->

[Your solutions here]

COMP382 Homework 6

Student Responses

---

Problem 1: True or False

Part (a)

Claim: Any flow graph G has a maximum flow that does not include a cycle in which each edge has positive flow.

Answer: TRUE

Proof:

Suppose we have a maximum flow f that includes a cycle C where every edge has positive flow. Let δ = min{f(e) : e ∈ C} > 0 be the minimum flow on any edge in the cycle.

Define a new flow f' by reducing the flow on each edge in C by δ:

f'(e) = f(e) - δ for all e ∈ C
f'(e) = f(e) for all e ∉ C

The new flow f' is still feasible (all flows remain non-negative) and the flow value does not change: at each intermediate node in the cycle, the flow conservation is maintained because we reduce both incoming and outgoing flow by the same amount.

We can repeat this process of removing cycles with positive flow until no such cycles remain. At each step, the maximum flow value is preserved. Therefore, there exists a maximum flow with no cycles containing positive flow.

---

Part (b)

Claim: If all edges in a graph have distinct capacities, there is a unique maximum flow.

Answer: FALSE

Counterexample:

Consider a graph with 4 nodes: s, t, u, v, and edges:

s → u: capacity 1
s → v: capacity 2
u → v: capacity 3
u → t: capacity 1
v → t: capacity 2

Maximum flow value is 3.

Flow 1: Send 1 unit on path s → u → t, and 2 units on path s → v → t. (Flow value = 3)

Flow 2: Send 1 unit on path s → u → v → t, and 2 units on path s → v → t. (Flow value = 3)

Both are maximum flows with the same flow value, but they distribute the flow differently. Thus, the maximum flow is not unique despite all edge capacities being distinct.

---

Part (c)

Claim: If we multiply all edge capacities in a flow network by a positive number λ, then the minimum cut stays unchanged.

Answer: FALSE

Counterexample:

Consider a simple flow network with source s, sink t, and a single edge s → t with capacity c(s,t) = 5.

The minimum cut is {s → t} with capacity 5.

If we multiply all capacities by λ = 2, the edge capacity becomes 10, and the minimum cut is now {s → t} with capacity 10.

The cut value changed from 5 to 10 (scaled by factor λ). Therefore, the minimum cut value is not unchanged.

---

Part (d)

Claim: If we add a positive number λ to all edge capacities, then the minimum cut stays unchanged.

Answer: FALSE

Counterexample:

Consider the same network: source s, sink t, and single edge s → t with capacity 5.

The minimum cut is {s → t} with capacity 5.

If we add λ = 10 to all edge capacities, the capacity becomes 5 + 10 = 15.

The minimum cut is now {s → t} with capacity 15, which is different from the original value of 5.

In general, if the minimum cut has k edges, adding λ to all capacities increases the minimum cut value by k·λ. Since k ≥ 1, the minimum cut value changes.

---

Problem 2: Flow Reduction

Problem: Given a unit-capacity flow network, delete k edges to minimize the maximum s-t flow.

Algorithm:

Use a greedy algorithm:

Algorithm: MIN_FLOW_REDUCTION(G, s, t, k)

1. remaining_edges ← E  // all edges
2. current_graph ← G

3. for i = 1 to k do:
     best_edge ← null
     best_flow ← ∞

     for each edge e in remaining_edges do:
       G' ← remove edge e from current_graph
       flow_value ← MAX_FLOW(G', s, t)

       if flow_value < best_flow then:
         best_flow ← flow_value
         best_edge ← e

     // Remove the edge that most reduces the flow
     current_graph ← remove edge best_edge from current_graph
     remaining_edges ← remaining_edges - {best_edge}

4. return remaining_edges

Justification:

The greedy approach is correct because we want to remove k edges such that the resulting maximum flow is minimized. At each iteration, we remove the edge whose deletion causes the maximum reduction in maximum flow. This ensures that we make the locally optimal choice at each step.

Complexity Analysis:

Let MaxFlow(V, E) denote the complexity of computing maximum flow in a graph with V vertices and E edges.

Outer loop: k iterations
Inner loop: |E| edge candidates
For each candidate: compute MAX_FLOW using Edmonds-Karp: O(VE²)

Total complexity: O(k · |E| · |V| · |E|²) = O(k · V · E³)

Using Dinic's algorithm for MAX_FLOW improves this to: O(k · E · V² · E log V) = O(k · V² · E² · log V)

This is polynomial in all input parameters with k not in an exponent.

---

Problem 3: Node Capacities

Problem: Find maximum s-t flow in a network where nodes have capacity constraints.

Algorithm:

Transform the node-capacitated flow problem into a standard edge-capacitated flow problem by splitting nodes.

Algorithm: SOLVE_NODE_CAPACITY_FLOW(G, s, t, c_v)

1. Create new graph G' = (V', E')

2. for each node v in V:
     if v == s or v == t then:
       // Source and sink are not split
       add v to V'
     else:
       // Split non-source/sink nodes
       add v_in and v_out to V'
       add edge (v_in, v_out) to E' with capacity c_v

3. for each edge (u, v) in E:
     if u == s then:
       add edge (s, v_in or v) to E' with capacity c(u,v)
     else if v == t then:
       add edge (u_out or u, t) to E' with capacity c(u,v)
     else:
       add edge (u_out, v_in) to E' with capacity c(u,v)

4. Run MAX_FLOW(G', s, t) using standard algorithm
5. return maximum flow value and flow decomposition

Justification:

By splitting each node v (except s and t) into v_in and v_out with capacity c_v on the connecting edge, we enforce the node capacity constraint. The maximum flow in G' equals the maximum flow in the original node-capacitated graph G.

To recover the node flow constraints: For each node v, the flow through v is bounded by f(v_in, v_out) ≤ c_v.

Complexity:

The transformed graph has V' = 2V - 2 vertices (s and t are not split) and E' = E + (V - 2) edges.

Using Dinic's algorithm: O(V'² · E' · log V') = O(V² · E · log V)

Or using Edmonds-Karp: O(V' · E'³) = O(V · E³)

---

Problem 4: Station Closing

Problem: Find the minimum number of stations to close (except A and B) to disconnect all paths from A to B.

This is a minimum vertex cut problem.

Algorithm:

Transform the vertex connectivity problem into an edge cut problem:

Algorithm: MIN_STATIONS_TO_CLOSE(G, A, B)

1. Create transformed graph G' = (V', E')

2. for each vertex v in G:
     if v == A or v == B then:
       // A and B are not split
       add v to V'
     else:
       // Split each other station into v_in and v_out
       add v_in and v_out to V'
       add edge (v_in, v_out) to E' with capacity 1
       // Capacity 1 represents: closing the station removes all flow

3. for each edge (u, v) in G:
     // Edges in original graph become edges between split nodes
     add edge from u_out to v_in in E' with capacity ∞
     add edge from v_out to u_in in E' with capacity ∞
     // Capacity ∞ because original edges don't have capacity limits

4. max_flow_value ← MAX_FLOW(G', A, B)
5. return max_flow_value  // This equals minimum stations to close

Justification:

By splitting each station v into v_in and v_out with capacity 1, we ensure that the flow through v is at most 1. The minimum cut in G' directly corresponds to the minimum vertex cut in the original graph. The maximum flow equals the minimum number of stations that must be closed to disconnect A from B.

Complexity:

Using Dinic's algorithm: O(V² · E · log V)

The transformed graph has O(V) vertices and O(E) edges, so the complexity is polynomial in V and E.

---

Problem 5: Exam Scheduling

Problem: Assign each of n classes to a room-time pair such that class i is assigned to room j only if E[i] < S[j], and at most one class per room per time slot.

Algorithm:

Model this as a maximum flow problem:

Algorithm: SCHEDULE_EXAMS(E[1..n], S[1..r], t)

1. Create flow network G = (V, E)
   V = {s, t, class_1, ..., class_n, room_1_1, ..., room_r_t, sink}
   // room_j_k represents room j at time slot k

2. Add source-to-class edges:
   for i = 1 to n:
     add edge (s, class_i) with capacity E[i]

3. Add class-to-room-time edges:
   for i = 1 to n:
     for j = 1 to r:
       for k = 1 to t:
         if E[i] < S[j] then:
           add edge (class_i, room_j_k) with capacity E[i]

4. Add room-time-to-sink edges:
   for j = 1 to r:
     for k = 1 to t:
       add edge (room_j_k, sink) with capacity S[j]

5. max_flow ← MAX_FLOW(G, s, sink)

6. if max_flow == Σ(E[i]) then:
     // All classes can be assigned
     for i = 1 to n:
       find room_j_k receiving all E[i] units of flow from class_i
       assign class_i to room j at time slot k
     return assignment
   else:
     return "NO ASSIGNMENT POSSIBLE"

Justification:

The source-to-class edges enforce that class i demands E[i] units (must accommodate all students). The class-to-room-time edges enforce the constraint E[i] < S[j] (class i can only use room j if it has enough capacity). The room-time-to-sink edges enforce that room j at time slot k can accommodate at most S[j] students. If the maximum flow equals the total demand Σ E[i], a valid assignment exists and can be recovered from the flow.

Complexity Analysis:

Number of vertices: V = 1 + n + (r × t) + 1 = O(nrt)
Number of edges: E = n + n·r·t + r·t = O(nrt)

Using Edmonds-Karp: O(V · E³) = O(nrt · (nrt)³) = O(n⁴r⁴t⁴)

Using Dinic's algorithm: O(V² · E) = O((nrt)² · nrt) = O(n³r³t³) or more precisely O(V²E log(maxflow)) which is typically much faster in practice.

Therefore, the complexity is O(n³r³t³) or better, which is polynomial in n, r, and t.

Now let me carefully grade each problem.

Problem 1: True or False

Score: 10/20 points

Assessment:

Part (a): 5/5

Approach: Student correctly identifies TRUE and provides a rigorous proof by contradiction/construction.

Strengths:

Correctly defines δ = min{f(e) : e ∈ C} as the minimum flow on the cycle
Clearly shows the new flow f' is feasible (non-negative) and value-preserving
Notes that flow conservation is maintained because both incoming and outgoing flow at each node in the cycle decrease by the same amount
Argues the process can be repeated until no positive-flow cycles remain

Errors/Gaps: None. This is a complete and correct proof, matching the reference solution.

Rubric Breakdown:

Correct answer (TRUE): 2/2
Valid proof: 3/3

---

Part (b): 2/5

Approach: Student correctly identifies FALSE and attempts a counterexample.

Errors/Gaps:

Critical error: The counterexample uses capacities {1, 2, 3, 1, 2} — capacity 1 appears on both (s→u) and (u→t), and capacity 2 appears on both (s→v) and (v→t). The hypothesis requires all edges to have distinct capacities, which is violated.
Second error: "Flow 2" (sending 1 unit on s→u→v→t and 2 units on s→v→t) is actually infeasible: the edge v→t would carry 3 units (1 from u→v→t + 2 from s→v→t), exceeding its capacity of 2.
In fact, the max flow in this graph is uniquely determined: s→u=1, u→t=1, s→v=2, v→t=2, u→v=0 (forced by capacity constraints).

Rubric Breakdown:

Correct answer (FALSE): 2/2
Valid counterexample: 0/3 — capacities not distinct, and claimed second flow is infeasible

---

Part (c): 1/5

Approach: Student incorrectly answers FALSE.

Errors/Gaps:

Fundamental misunderstanding: The question asks whether the minimum cut (i.e., the partition (S,T) that achieves the minimum) stays the same, not whether the cut value stays the same.
The student's "counterexample" uses a single-edge graph (s→t). In this graph there is only one possible cut, so the minimum cut trivially remains unchanged regardless of scaling — the student's own example contradicts their answer.
The reference solution correctly notes: "The value of each cut gets multiplied by λ. Thus, the relative order of cuts does not change." This is because if cut C₁ < C₂ before scaling, then λC₁ < λC₂ after scaling (for λ > 0).

Rubric Breakdown:

Correct answer: 0/2 (answered FALSE, correct is TRUE)
Reasoning: 1/3 (recognizes the value scales by λ, but draws the wrong conclusion)

---

Part (d): 2/5

Approach: Student correctly identifies FALSE.

Errors/Gaps:

The counterexample again uses a single-edge graph where there is only one possible cut partition. Since the partition cannot change (there's only one), this counterexample fails to demonstrate that the minimum cut partition changes.
The student's general observation — "if the minimum cut has k edges, adding λ increases the cut value by kλ" — is the key insight but is not fully developed. The correct argument is: different cuts may have different numbers of edges, so adding λ affects them differently, potentially changing which cut is minimum. The reference solution demonstrates this with a concrete multi-cut graph.
The student stops short of making the critical connection that cuts with fewer edges gain less capacity, potentially becoming the new minimum.

Rubric Breakdown:

Correct answer (FALSE): 2/2
Valid counterexample/proof: 0/3 — counterexample doesn't work; general argument is incomplete

---

Problem 2: Flow Reduction

Score: 10/20 points

Assessment:

Approach: The student proposes a greedy algorithm that iteratively removes the single edge whose deletion most reduces the maximum flow, repeating k times.

Strengths:

The algorithm is polynomial-time (k does not appear in the exponent), satisfying the problem's constraint
The algorithm is clearly described with pseudocode
The complexity analysis is correct for the greedy approach

Errors/Gaps:

Missing the key insight: The reference solution uses a much more elegant approach: find the min s-t cut, then remove k edges from it. This immediately gives the optimal answer in one max-flow computation.
No proof of optimality: The student claims "the greedy approach is correct because... we make the locally optimal choice at each step." This is hand-waving — greedy algorithms are not always globally optimal, and the student provides no exchange argument or other proof technique. In fact, the greedy approach *does* work here (in unit-capacity networks, removing a min-cut edge always reduces flow by exactly 1, which is the best possible per-edge reduction), but the student doesn't prove this.
Missing the optimality bound: The reference proves that no set of k edge removals can reduce the flow by more than k (using a cut-capacity argument). This is the crucial insight the student misses entirely.
Excessive complexity: The student's algorithm runs k × |E| max-flow computations, giving O(k·V·E³) with Edmonds-Karp. The reference solution runs one max-flow computation: O(VE²).

Rubric Breakdown:

Correct polynomial-time algorithm: 5/8
Proof of optimality: 1/8 (hand-waving only)
Complexity analysis: 4/4 (correct for their algorithm)

---

Problem 3: Node Capacities

Score: 16/20 points

Assessment:

Approach: The student correctly transforms the node-capacitated network by splitting each non-source/sink node v into v_in and v_out, connected by an edge with capacity c_v. This is the standard and correct approach.

Strengths:

Correctly identifies the node-splitting technique
Properly handles source and sink as special cases (not split)
Clear pseudocode with explicit handling of edge redirection
Justification captures the key correctness argument: node capacity enforced via internal edge

Errors/Gaps:

Edge capacity ambiguity: The problem specifies only node capacities (no edge capacities), but the student writes "capacity c(u,v)" for redirected edges, implying edge capacities exist. The reference solution uses infinite capacity for these edges (since edges are unconstrained). While the student's approach would work if c(u,v) = ∞, the notation is imprecise and suggests a misreading of the problem.
Complexity formula error: The student cites Dinic's algorithm as "O(V'² · E' · log V')" — Dinic's algorithm is O(V²E), not O(V²E log V). Similarly, Edmonds-Karp is O(VE²), not O(VE³).
The correctness justification, while adequate, is less rigorous than the reference's explicit bidirectional argument (flow in new graph ↔ flow in original graph).

Rubric Breakdown:

Correct transformation: 8/8
Correctness proof: 4/6 (adequate but could be more rigorous; edge capacity imprecision)
Complexity analysis: 4/6 (transformation size correct; max-flow complexity formulas have errors)

---

Problem 4: Station Closing

Score: 14/20 points

Assessment:

Approach: The student correctly identifies this as a minimum vertex cut problem and uses the node-splitting technique to transform it into a max-flow problem.

Strengths:

Correctly recognizes minimum vertex cut as the core problem
Proper node splitting: each station (except A, B) becomes v_in → v_out with capacity 1
Correct use of infinite capacity for original edges
Correctly handles both directions of undirected edges
Clear pseudocode

Errors/Gaps:

Incomplete specification for A and B: The student states A and B are not split (just added as single nodes), but the edge construction rule says "add edge from u_out to v_in" for ALL edges. When u = A, the node A_out doesn't exist (since A wasn't split). The algorithm as written is undefined for edges incident to A or B. The reference solution splits ALL nodes (including A, B) and uses s = A_out, t = B_in, elegantly avoiding this issue.
Missing edge case: The reference solution explicitly addresses the case where A and B are directly connected by a rail line, noting the assumption (A,B) ∉ E. The student doesn't discuss this case. If A and B are directly connected, you cannot block travel between them (since neither station can be closed), so the problem has no solution — this should be mentioned.
Source/sink definition: Using "A" and "B" as source/sink without clarifying how edges connect to unsplit nodes is imprecise.

Rubric Breakdown:

Correct transformation concept: 7/8
Correctness proof: 4/6 (correct reasoning but missing edge cases and A/B handling)
Complexity analysis: 3/6 (stated but not detailed; no discussion of graph construction cost)

---

Problem 5: Exam Scheduling

Score: 6/20 points

Assessment:

Approach: The student models the problem as a max-flow network, creating room-time combination nodes (room_j_k). However, the model routes students to room-time slots rather than assigning classes to room-time pairs, fundamentally mismodeling the problem.

Strengths:

Correctly identifies this as a max-flow problem
Incorporates the E[i] < S[j] room eligibility constraint
Creates room-time combination nodes (a reasonable structural idea)
Provides complexity analysis

Errors/Gaps:

Fundamental modeling error: The student uses capacities based on student counts (E[i] from source to class, E[i] on class-to-room edges, S[j] on room-to-sink edges). This models student routing, not class assignment. The critical constraint — "at most one final exam can be held in each room during each time slot" — is not enforced.

Concrete counterexample: Consider 3 classes (E = [3, 3, 3]), 2 rooms (S = [5, 5]), 1 time slot. The student's model achieves max flow = 9 = ΣE[i] by splitting students across rooms (e.g., 5 students in room 1, 4 in room 2). But no valid assignment exists: there are only 2 room-time pairs for 3 classes.

Incorrect check condition: The student checks if max flow = ΣE[i], but this can be satisfied even when no valid assignment exists (as shown above).

Reference solution comparison: The reference uses capacity-1 edges throughout:

- Source → class: capacity 1 (one assignment per class) - Class → room: capacity 1 (if E[i] < S[j]) - Room → time: capacity 1 (one exam per room per time) - Time → sink: capacity r - Valid iff max flow = n (number of classes)

This correctly models assignment (not routing) and enforces the one-exam-per-room-per-slot constraint.

Rubric Breakdown:

Problem understanding (flow-based approach): 2/4
Correct network construction: 2/8 (some structural elements correct, but fundamental model is wrong)
Correctness justification: 1/4 (follows logically from wrong model)
Complexity analysis: 1/4 (correct for the wrong model)

---

Overall Summary

Problem	Score	Notes
1(a)	5/5	Correct, well-proven
1(b)	2/5	Correct answer; counterexample has non-distinct capacities and infeasible flow
1(c)	1/5	Wrong answer (FALSE instead of TRUE); misinterprets "cut stays unchanged"
1(d)	2/5	Correct answer; counterexample doesn't demonstrate partition change
1 Total	10/20
2	10/20	Greedy algorithm works but no optimality proof; misses min-cut insight
3	16/20	Correct node-splitting; imprecise edge capacities; minor complexity errors
4	14/20	Correct vertex-cut approach; incomplete A/B handling; missing edge case
5	6/20	Fundamentally wrong model — routes students instead of assigning classes
Total	56/100

General Comments:

The student demonstrates solid understanding of the node-splitting technique (Problems 3 and 4) and general familiarity with network flow concepts. The True/False section reveals gaps in understanding what "minimum cut" refers to (the partition, not the value). Problem 2 shows the student can construct algorithms but lacks the theoretical rigor to prove optimality — the key min-cut insight was missed entirely. The most significant weakness is Problem 5, where the flow network fundamentally mismodels the assignment problem by routing students rather than assigning classes to room-time slots, failing to enforce the one-exam-per-room-per-slot constraint. Going forward, the student should practice: (1) constructing valid counterexamples that satisfy all problem hypotheses, (2) proving algorithm optimality rather than relying on greedy intuition, and (3) carefully distinguishing between assignment/matching problems and routing problems in flow network constructions.

Total: 56/100

writeup.md

diff --git a/writeup.md b/writeup.md
index eda66f5..c91f6ea 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,297 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: True or False
 
+### Part (a)
+
+**Claim:** Any flow graph G has a maximum flow that does not include a cycle in which each edge has positive flow.
+
+**Answer: TRUE**
+
+**Proof:**
+
+Suppose we have a maximum flow f that includes a cycle C where every edge has positive flow. Let δ = min{f(e) : e ∈ C} > 0 be the minimum flow on any edge in the cycle.
+
+Define a new flow f' by reducing the flow on each edge in C by δ:
+- f'(e) = f(e) - δ for all e ∈ C
+- f'(e) = f(e) for all e ∉ C
+
+The new flow f' is still feasible (all flows remain non-negative) and the flow value does not change: at each intermediate node in the cycle, the flow conservation is maintained because we reduce both incoming and outgoing flow by the same amount.
+
+We can repeat this process of removing cycles with positive flow until no such cycles remain. At each step, the maximum flow value is preserved. Therefore, there exists a maximum flow with no cycles containing positive flow.
+
+---
+
+### Part (b)
+
+**Claim:** If all edges in a graph have distinct capacities, there is a unique maximum flow.
+
+**Answer: FALSE**
+
+**Counterexample:**
+
+Consider a graph with 4 nodes: s, t, u, v, and edges:
+- s → u: capacity 1
+- s → v: capacity 2
+- u → v: capacity 3
+- u → t: capacity 1
+- v → t: capacity 2
+
+Maximum flow value is 3.
+
+Flow 1: Send 1 unit on path s → u → t, and 2 units on path s → v → t. (Flow value = 3)
+
+Flow 2: Send 1 unit on path s → u → v → t, and 2 units on path s → v → t. (Flow value = 3)
+
+Both are maximum flows with the same flow value, but they distribute the flow differently. Thus, the maximum flow is not unique despite all edge capacities being distinct.
+
+---
+
+### Part (c)
+
+**Claim:** If we multiply all edge capacities in a flow network by a positive number λ, then the minimum cut stays unchanged.
+
+**Answer: FALSE**
+
+**Counterexample:**
+
+Consider a simple flow network with source s, sink t, and a single edge s → t with capacity c(s,t) = 5.
+
+The minimum cut is {s → t} with capacity 5.
+
+If we multiply all capacities by λ = 2, the edge capacity becomes 10, and the minimum cut is now {s → t} with capacity 10.
+
+The cut value changed from 5 to 10 (scaled by factor λ). Therefore, the minimum cut value is not unchanged.
+
+---
+
+### Part (d)
+
+**Claim:** If we add a positive number λ to all edge capacities, then the minimum cut stays unchanged.
+
+**Answer: FALSE**
+
+**Counterexample:**
+
+Consider the same network: source s, sink t, and single edge s → t with capacity 5.
+
+The minimum cut is {s → t} with capacity 5.
+
+If we add λ = 10 to all edge capacities, the capacity becomes 5 + 10 = 15.
+
+The minimum cut is now {s → t} with capacity 15, which is different from the original value of 5.
+
+In general, if the minimum cut has k edges, adding λ to all capacities increases the minimum cut value by k·λ. Since k ≥ 1, the minimum cut value changes.
+
+---
+
+## Problem 2: Flow Reduction
+
+**Problem:** Given a unit-capacity flow network, delete k edges to minimize the maximum s-t flow.
+
+**Algorithm:**
+
+Use a greedy algorithm:
+
+```
+Algorithm: MIN_FLOW_REDUCTION(G, s, t, k)
+
+1. remaining_edges ← E  // all edges
+2. current_graph ← G
+
+3. for i = 1 to k do:
+     best_edge ← null
+     best_flow ← ∞
+
+     for each edge e in remaining_edges do:
+       G' ← remove edge e from current_graph
+       flow_value ← MAX_FLOW(G', s, t)
+
+       if flow_value < best_flow then:
+         best_flow ← flow_value
+         best_edge ← e
+
+     // Remove the edge that most reduces the flow
+     current_graph ← remove edge best_edge from current_graph
+     remaining_edges ← remaining_edges - {best_edge}
+
+4. return remaining_edges
+```
+
+**Justification:**
+
+The greedy approach is correct because we want to remove k edges such that the resulting maximum flow is minimized. At each iteration, we remove the edge whose deletion causes the maximum reduction in maximum flow. This ensures that we make the locally optimal choice at each step.
+
+**Complexity Analysis:**
+
+Let MaxFlow(V, E) denote the complexity of computing maximum flow in a graph with V vertices and E edges.
+
+- Outer loop: k iterations
+- Inner loop: |E| edge candidates
+- For each candidate: compute MAX_FLOW using Edmonds-Karp: O(VE²)
+
+Total complexity: **O(k · |E| · |V| · |E|²) = O(k · V · E³)**
+
+Using Dinic's algorithm for MAX_FLOW improves this to: **O(k · E · V² · E log V) = O(k · V² · E² · log V)**
+
+This is polynomial in all input parameters with k not in an exponent.
+
+---
+
+## Problem 3: Node Capacities
+
+**Problem:** Find maximum s-t flow in a network where nodes have capacity constraints.
+
+**Algorithm:**
+
+Transform the node-capacitated flow problem into a standard edge-capacitated flow problem by splitting nodes.
+
+```
+Algorithm: SOLVE_NODE_CAPACITY_FLOW(G, s, t, c_v)
+
+1. Create new graph G' = (V', E')
+
+2. for each node v in V:
+     if v == s or v == t then:
+       // Source and sink are not split
+       add v to V'
+     else:
+       // Split non-source/sink nodes
+       add v_in and v_out to V'
+       add edge (v_in, v_out) to E' with capacity c_v
+
+3. for each edge (u, v) in E:
+     if u == s then:
+       add edge (s, v_in or v) to E' with capacity c(u,v)
+     else if v == t then:
+       add edge (u_out or u, t) to E' with capacity c(u,v)
+     else:
+       add edge (u_out, v_in) to E' with capacity c(u,v)
+
+4. Run MAX_FLOW(G', s, t) using standard algorithm
+5. return maximum flow value and flow decomposition
+```
+
+**Justification:**
+
+By splitting each node v (except s and t) into v_in and v_out with capacity c_v on the connecting edge, we enforce the node capacity constraint. The maximum flow in G' equals the maximum flow in the original node-capacitated graph G.
+
+To recover the node flow constraints: For each node v, the flow through v is bounded by f(v_in, v_out) ≤ c_v.
+
+**Complexity:**
+
+The transformed graph has V' = 2V - 2 vertices (s and t are not split) and E' = E + (V - 2) edges.
+
+Using Dinic's algorithm: **O(V'² · E' · log V') = O(V² · E · log V)**
+
+Or using Edmonds-Karp: **O(V' · E'³) = O(V · E³)**
+
+---
+
+## Problem 4: Station Closing
+
+**Problem:** Find the minimum number of stations to close (except A and B) to disconnect all paths from A to B.
+
+This is a **minimum vertex cut** problem.
+
+**Algorithm:**
+
+Transform the vertex connectivity problem into an edge cut problem:
+
+```
+Algorithm: MIN_STATIONS_TO_CLOSE(G, A, B)
+
+1. Create transformed graph G' = (V', E')
+
+2. for each vertex v in G:
+     if v == A or v == B then:
+       // A and B are not split
+       add v to V'
+     else:
+       // Split each other station into v_in and v_out
+       add v_in and v_out to V'
+       add edge (v_in, v_out) to E' with capacity 1
+       // Capacity 1 represents: closing the station removes all flow
+
+3. for each edge (u, v) in G:
+     // Edges in original graph become edges between split nodes
+     add edge from u_out to v_in in E' with capacity ∞
+     add edge from v_out to u_in in E' with capacity ∞
+     // Capacity ∞ because original edges don't have capacity limits
+
+4. max_flow_value ← MAX_FLOW(G', A, B)
+5. return max_flow_value  // This equals minimum stations to close
+```
+
+**Justification:**
+
+By splitting each station v into v_in and v_out with capacity 1, we ensure that the flow through v is at most 1. The minimum cut in G' directly corresponds to the minimum vertex cut in the original graph. The maximum flow equals the minimum number of stations that must be closed to disconnect A from B.
+
+**Complexity:**
+
+Using Dinic's algorithm: **O(V² · E · log V)**
+
+The transformed graph has O(V) vertices and O(E) edges, so the complexity is **polynomial in V and E**.
+
+---
+
+## Problem 5: Exam Scheduling
+
+**Problem:** Assign each of n classes to a room-time pair such that class i is assigned to room j only if E[i] < S[j], and at most one class per room per time slot.
+
+**Algorithm:**
+
+Model this as a maximum flow problem:
+
+```
+Algorithm: SCHEDULE_EXAMS(E[1..n], S[1..r], t)
+
+1. Create flow network G = (V, E)
+   V = {s, t, class_1, ..., class_n, room_1_1, ..., room_r_t, sink}
+   // room_j_k represents room j at time slot k
+
+2. Add source-to-class edges:
+   for i = 1 to n:
+     add edge (s, class_i) with capacity E[i]
+
+3. Add class-to-room-time edges:
+   for i = 1 to n:
+     for j = 1 to r:
+       for k = 1 to t:
+         if E[i] < S[j] then:
+           add edge (class_i, room_j_k) with capacity E[i]
+
+4. Add room-time-to-sink edges:
+   for j = 1 to r:
+     for k = 1 to t:
+       add edge (room_j_k, sink) with capacity S[j]
+
+5. max_flow ← MAX_FLOW(G, s, sink)
+
+6. if max_flow == Σ(E[i]) then:
+     // All classes can be assigned
+     for i = 1 to n:
+       find room_j_k receiving all E[i] units of flow from class_i
+       assign class_i to room j at time slot k
+     return assignment
+   else:
+     return "NO ASSIGNMENT POSSIBLE"
+```
+
+**Justification:**
+
+The source-to-class edges enforce that class i demands E[i] units (must accommodate all students). The class-to-room-time edges enforce the constraint E[i] < S[j] (class i can only use room j if it has enough capacity). The room-time-to-sink edges enforce that room j at time slot k can accommodate at most S[j] students. If the maximum flow equals the total demand Σ E[i], a valid assignment exists and can be recovered from the flow.
+
+**Complexity Analysis:**
+
+- Number of vertices: V = 1 + n + (r × t) + 1 = O(nrt)
+- Number of edges: E = n + n·r·t + r·t = O(nrt)
+
+Using Edmonds-Karp: **O(V · E³) = O(nrt · (nrt)³) = O(n⁴r⁴t⁴)**
+
+Using Dinic's algorithm: **O(V² · E) = O((nrt)² · nrt) = O(n³r³t³)** or more precisely **O(V²E log(maxflow))** which is typically much faster in practice.
+
+Therefore, the complexity is **O(n³r³t³)** or better, which is polynomial in n, r, and t.

Agent Work: Homework6

COMP 382: Reasoning about Algorithms

Homework 6

Problem 1: True or False [20 points]

Part (a)

Part (b)

Part (c)

Part (d)

Problem 2: Flow Reduction [20 points]

Problem 3: Node Capacities [20 points]

Problem 4: Station Closing [20 points]

Problem 5: Exam Scheduling [20 points]

COMP382 Homework 6

Student Responses

Problem 1: True or False

Part (a)

Part (b)

Part (c)

Part (d)

Problem 2: Flow Reduction

Problem 3: Node Capacities

Problem 4: Station Closing

Problem 5: Exam Scheduling

Problem 1: True or False

Score: 10/20 points

Assessment:

Problem 2: Flow Reduction

Score: 10/20 points

Assessment:

Problem 3: Node Capacities

Score: 16/20 points

Assessment:

Problem 4: Station Closing

Score: 14/20 points

Assessment:

Problem 5: Exam Scheduling

Score: 6/20 points

Assessment:

Overall Summary

General Comments:

Sub-Model Usage