Agent Work: Homework7

Claude Haiku 4.5 · COMP 382: Reasoning about Algorithms

COMP 382: Reasoning about Algorithms

Homework 7

Total Points: 100 (NP-Completeness Reductions)

Note: Solutions to polynomial-time mapping reductions must be accompanied by proofs of correctness.

---

Problem 1: Efficient Recruiting [25 points]

Suppose you are helping organize a summer camp. The camp is supposed to have at least one counselor who is skilled at each of the n sports covered by the camp (baseball, volleyball, and so on). They have received job applicants from m potential counselors. For each of the n sports, there is a subset of the m applicants qualified in that sport.

The question is: For a given number k < m, is it possible to hire at most k of the counselors and have at least one counselor qualified in each of the n sports? We'll call this the *Efficient Recruiting* problem.

Show that Vertex Cover ≤ₚ Efficient Recruiting.

---

Problem 2: Plot Fulfillment [25 points]

Hypertext fiction is a type of fiction consisting of a set of pages, each containing some text, along with links between them. The reader of such a hypertext story follows a *trail* — a sequence of pages that begins with a *start page* s and finishes at an *end page* t — through the story.

Suppose you have created a piece of hypertext fiction, and you would like to know if there is a trail through your story that contains each of a set of *thematic elements*. You have n thematic elements, the i-th of which can be identified with a set Tᵢ of pages.

We formalize this as the *Plot Fulfillment* problem, which asks: is there a trail from s to t that contains at least one page from each of the sets Tᵢ?

Show that Hitting Set ≤ₚ Plot Fulfillment.

---

Problem 3: Path Selection [25 points]

Suppose you are managing a communication network, modeled by a directed graph G = (V, E). There are c users who want to use the network. User i (we have 1 ≤ i ≤ c) issues a *request* to reserve a specific path Pᵢ in G on which to transmit data.

You want to accept as many path requests as possible, except if you accept Pᵢ and Pⱼ, then Pᵢ and Pⱼ cannot share any nodes.

The *Path Selection* problem formalizes this intent. It asks: Given a directed graph G = (V, E), a set of path requests P₁, ..., Pₓ, and a number k, is it possible to select at least k of the paths so that no two of the selected paths share any nodes?

Show that Independent Set ≤ₚ Path Selection.

---

Problem 4: Half 3-SAT Satisfiability [25 points]

Given a 3-SAT formula φ with n variables and m clauses, where m is even. We wish to determine whether there is a truth assignment to the variables of φ such that exactly half the clauses evaluate to true and half the clauses evaluate to false.

Show that 3-SAT ≤ₚ Half 3-SAT Satisfiability.

writeup.md206 B

markdown

# COMP382 Homework 7

## Student Responses

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

[Your solutions here]

COMP382 Homework 7: NP-Completeness Reductions

Problem 1: Efficient Recruiting [25 points]

Claim: Vertex Cover ≤ₚ Efficient Recruiting

Reduction:

Given a Vertex Cover instance consisting of:

Graph G = (V, E) where |V| = n and |E| = m
Integer k (determine if there is a vertex cover of size ≤ k)

We construct an Efficient Recruiting instance as follows:

Construction:

Sports: Create one sport for each edge in E. We have m sports total.
Counselors: Create one counselor for each vertex in V. We have n counselors total.
Qualifications: For each edge e = (u, v) ∈ E, the counselors corresponding to vertices u and v are qualified for sport e (these are the only two qualified).
Threshold: k (same as the vertex cover threshold)

Proof of Correctness:

Direction 1 (YES for VC → YES for ER): Suppose there exists a vertex cover S ⊆ V with |S| ≤ k. By definition of vertex cover, every edge has at least one endpoint in S. Therefore, for each sport (corresponding to edge e = (u,v)), at least one of the two qualified counselors (corresponding to u or v) is in S. If we hire exactly the counselors in S, all m sports have at least one qualified counselor, and we've hired at most k counselors.

Direction 2 (NO for VC → NO for ER): Conversely, suppose there is no vertex cover of size ≤ k. If we could hire at most k counselors to cover all m sports, then for each sport (edge e = (u,v)), at least one of the corresponding counselors is hired. This means the set of hired counselors is a vertex cover of G. But this contradicts our assumption that no vertex cover of size ≤ k exists. Therefore, it's impossible to hire ≤ k counselors to cover all sports.

Conclusion: The reduction is polynomial time and preserves the answer. Therefore, Vertex Cover ≤ₚ Efficient Recruiting. ✓

---

Problem 2: Plot Fulfillment [25 points]

Claim: Hitting Set ≤ₚ Plot Fulfillment

Reduction:

Given a Hitting Set instance consisting of:

Universe U = {u₁, u₂, ..., u_ℓ}
Sets S₁, S₂, ..., S_n where each Sᵢ ⊆ U
Integer k (determine if there is a hitting set of size ≤ k)

We construct a Plot Fulfillment instance (hypertext) as follows:

Construction:

Pages: Create pages {s, c₁, c₂, ..., c_{n-1}, t} ∪ U

- s = start page - t = end page - c₁, ..., c_{n-1} = checkpoint pages - U itself provides the remaining pages

Thematic Elements: For i = 1 to n, let Tᵢ = Sᵢ

Links (directed graph edges):

- From s to each element u ∈ S₁ - For i = 1 to n-1: - From each u ∈ Sᵢ to checkpoint c_i - From checkpoint c_i to each element in S_{i+1} - From each u ∈ S_n to t

Key structure: This creates a "chain" where any trail from s to t must pass through sequential sets, selecting at least one element from each set along the way.

Proof of Correctness:

The graph structure forces any path from s to t to have the form:

s → p₁ → c₁ → p₂ → c₂ → ... → c_{n-1} → p_n → t

where pᵢ ∈ Sᵢ for each i = 1 to n.

Direction 1 (YES for HS → YES for PF): If there exists a hitting set H (which hits all sets), then for each i, there exists an element hᵢ ∈ H ∩ Sᵢ. We can construct the trail:

s → h₁ → c₁ → h₂ → c₂ → ... → c_{n-1} → h_n → t

This trail connects s to t and contains at least one page from each thematic element Tᵢ.

Direction 2 (YES for PF → YES for HS): If there exists a trail from s to t containing pages from all thematic elements, then by the graph structure, the trail must be of the form above with pᵢ ∈ Sᵢ. The set {p₁, p₂, ..., p_n} forms a hitting set: it contains at least one element from each set Sᵢ.

Conclusion: The reduction is polynomial time and preserves YES/NO answers. Therefore, Hitting Set ≤ₚ Plot Fulfillment. ✓

---

Problem 3: Path Selection [25 points]

Claim: Independent Set ≤ₚ Path Selection

Reduction:

Given an Independent Set instance consisting of:

Graph G = (V, E) with V = {v₁, v₂, ..., v_n}
Integer k (determine if there is an independent set of size ≤ k)

We construct a Path Selection instance as follows:

Construction:

Graph: Use the same graph G = (V, E)
Path requests: For each vertex vᵢ ∈ V, define path request Pᵢ as a single-node path: Pᵢ = (vᵢ)
Threshold: k (determine if we can select at least k node-disjoint paths)

Proof of Correctness:

Direction 1 (YES for IS → YES for PS): Suppose there exists an independent set S ⊆ V with |S| ≤ k such that no two vertices in S are adjacent. Consider the set of paths {Pᵢ : vᵢ ∈ S}. Each path is a single node, so two paths share a node if and only if they correspond to the same vertex. Since all vertices in S are distinct, these k paths are node-disjoint. Therefore, we can select at least k node-disjoint paths.

Direction 2 (YES for PS → YES for IS): Conversely, suppose we can select at least k paths that are node-disjoint. Since each path Pᵢ consists only of the single node vᵢ, k node-disjoint paths correspond to k distinct vertices. Moreover, these vertices cannot have edges between them (as an edge e = (u,v) would mean paths Pᵤ and Pᵥ both contain nodes u and v, violating node-disjointness). Thus, these k vertices form an independent set.

Conclusion: The reduction is polynomial time and preserves YES/NO answers. Therefore, Independent Set ≤ₚ Path Selection. ✓

---

Problem 4: Half 3-SAT Satisfiability [25 points]

Claim: 3-SAT ≤ₚ Half 3-SAT Satisfiability

Reduction:

Given a 3-SAT instance consisting of:

Variables x₁, x₂, ..., x_n
m clauses C₁, C₂, ..., C_m where each Cᵢ is a disjunction of exactly three literals

We construct a Half 3-SAT instance as follows:

Construction:

For each clause Cᵢ = (lᵢ₁ ∨ lᵢ₂ ∨ lᵢ₃) in the original formula:

1. Include the original clause: Add Cᵢ to the new formula 2. Include three negation unit clauses: If Cᵢ = (aᵢ ∨ bᵢ ∨ cᵢ), add the three clauses: - (¬aᵢ) - (¬bᵢ) - (¬cᵢ)

These three clauses together represent the negation of Cᵢ: namely, ¬Cᵢ = (¬aᵢ ∧ ¬bᵢ ∧ ¬cᵢ)

Total clauses in new formula: m + 3m = 4m clauses

Question: Does there exist an assignment satisfying exactly 2m out of 4m clauses?

Proof of Correctness:

We analyze how many clauses are satisfied based on how many original clauses are satisfied.

Suppose an assignment satisfies exactly k of the original m clauses. Then:

Original clauses satisfied: exactly k
Unit clauses satisfied: For the 3m unit clauses:

- If original clause Cᵢ is satisfied, then at least one of aᵢ, bᵢ, cᵢ is true, so at least one of the negations ¬aᵢ, ¬bᵢ, ¬cᵢ is false. This means at most 2 of the 3 corresponding unit clauses are satisfied. - If original clause Cᵢ is unsatisfied, then all of aᵢ, bᵢ, cᵢ are false, so all of ¬aᵢ, ¬bᵢ, ¬cᵢ are true. This means all 3 corresponding unit clauses are satisfied.

If k clauses are satisfied and m-k are unsatisfied: - From unsatisfied clauses: 3(m-k) unit clauses are satisfied - From satisfied clauses: 0 unit clauses are satisfied (since each satisfied clause makes at least one unit clause false) - Total unit clauses satisfied: 3(m-k)

Total clauses satisfied: k + 3(m-k) = k + 3m - 3k = 3m - 2k

Direction 1 (YES for 3-SAT → YES for Half 3-SAT): If the original 3-SAT instance is satisfiable, there exists an assignment satisfying all m original clauses (k = m). Under this assignment:

Total satisfied clauses = 3m - 2m = m
This is exactly half of 4m ✓

Direction 2 (NO for 3-SAT → NO for Half 3-SAT): If the original 3-SAT instance is unsatisfiable, then k < m for any assignment. Under any assignment where k < m:

Total satisfied clauses = 3m - 2k > 3m - 2m = m
This is MORE than half of 4m, so exactly m clauses cannot be satisfied

Therefore, exactly 2m clauses can be satisfied if and only if all original clauses are satisfiable.

Conclusion: The reduction is polynomial time and preserves YES/NO answers. Therefore, 3-SAT ≤ₚ Half 3-SAT Satisfiability. ✓

I'll read the relevant files to verify the problem details, then grade the submission carefully.

Problem 1: Efficient Recruiting [25 points]

Score: 25/25 points

Assessment:

Approach: The student maps vertices to counselors, edges to sports, and preserves the parameter k — identical to the reference solution.

Strengths:

Clean, correct construction: one sport per edge, one counselor per vertex, qualified iff incident
Both directions proved rigorously (forward and contrapositive of backward)
Polynomial-time argument implicit in the construction size
Clear presentation with labeled directions

Errors/Gaps:

None

Detailed Feedback: This is a complete, correct solution. The construction is exactly the natural reduction from Vertex Cover to Efficient Recruiting, and both directions of the correctness proof are clearly established. The student proves the forward direction (vertex cover → valid hiring) directly, and the backward direction via contrapositive (no vertex cover → no valid hiring), which is equivalent and perfectly valid.

Rubric Breakdown:

Construction (mapping): 10/10 — correct and complete
Forward direction proof: 5/5 — clear and rigorous
Backward direction proof: 5/5 — correct via contrapositive
Polynomial-time argument: 5/5 — evident from construction

---

Problem 2: Plot Fulfillment [25 points]

Score: 10/25 points

Assessment:

Approach: The student creates a chain of "checkpoint" pages between sets, with thematic elements Tᵢ = Sᵢ. Any trail from s to t must pass through one element from each set sequentially.

Strengths:

Correct reduction direction (Hitting Set → Plot Fulfillment)
Reasonable graph construction with a layered/chain structure
Both proof directions are attempted with clear presentation
The mapping of sets Sᵢ to thematic elements Tᵢ is a natural and correct starting point

Errors/Gaps:

Critical: The parameter k is never used in the construction. The Hitting Set problem asks whether a hitting set of size ≤ k exists, but the student's Plot Fulfillment instance has no mechanism to enforce a size bound. Plot Fulfillment only asks whether *any* trail from s to t hits all thematic elements — there is no budget parameter.
The reduction always produces YES instances: In the student's construction, as long as each Sᵢ is non-empty, a trail always exists: just pick any element from each set and thread through the checkpoints. This means NO instances of Hitting Set (where no small enough hitting set exists) are incorrectly mapped to YES instances of Plot Fulfillment.
Direction 2 is flawed: The student claims the trail elements form a hitting set, which is true, but never verifies that this hitting set has size ≤ k. The trail selects n elements (one per set, with possible repeats), and n could be much larger than k.

Detailed Feedback: The fundamental issue is that the size constraint k — the core of what makes Hitting Set hard — is completely absent from the construction. The reference solution handles this by creating a *layered* graph with exactly k layers, where each layer has one node per universe element. A path from s to t passes through exactly k layers, selecting exactly k elements, which naturally enforces the size-k constraint. The student's checkpoint structure forces visiting one element per *set* (of which there are n), not per "budget slot" (of which there should be k). Without encoding k, the reduction is fundamentally incorrect.

Rubric Breakdown:

Correct reduction direction: 3/5
Construction: 4/10 — reasonable structure but missing k
Forward direction proof: 2/5 — works but is nearly trivial given the construction
Backward direction proof: 0/5 — fundamentally flawed (k not enforced)
Polynomial time: 1/5 — mentioned implicitly

---

Problem 3: Path Selection [25 points]

Score: 5/25 points

Assessment:

Approach: The student uses the same graph G and creates a single-node path Pᵢ = (vᵢ) for each vertex vᵢ. They claim that paths are node-disjoint iff the corresponding vertices are non-adjacent.

Strengths:

Correct reduction direction (Independent Set → Path Selection)
Both proof directions are attempted
Clear presentation

Errors/Gaps:

Critical: Single-node paths cannot encode adjacency. Path Pᵤ = (u) contains only node u, and path Pᵥ = (v) contains only node v. These paths are node-disjoint whenever u ≠ v, *regardless of whether (u,v) is an edge in G*. The student's claim that "an edge e = (u,v) would mean paths Pᵤ and Pᵥ both contain nodes u and v" is false — Pᵤ contains only u, not v.
The reduction always produces YES instances: Since any k distinct single-node paths are trivially node-disjoint, the Path Selection instance always has answer YES (for k ≤ n), regardless of whether G has an independent set.
Wrong inequality for Independent Set: The student writes |S| ≤ k, but Independent Set asks for |S| ≥ k.

Detailed Feedback: The core problem is that single-node paths carry no structural information about adjacency. The reference solution is fundamentally different and much more clever: it creates a node uₑ for *each edge* e ∈ G, then builds a path Pᵥ for each vertex v that passes through all edge-nodes incident to v. This way, if two vertices v₁ and v₂ are adjacent via edge e, both paths Pᵥ₁ and Pᵥ₂ must pass through the shared node uₑ, making them non-disjoint. The student's construction completely misses this key insight of encoding adjacency through shared path nodes.

Rubric Breakdown:

Correct reduction direction: 3/5
Construction: 0/10 — fundamentally incorrect
Forward direction proof: 1/5 — technically valid but vacuous (trivially true for any k vertices)
Backward direction proof: 0/5 — contains a demonstrably false claim
Polynomial time: 1/5 — trivially true but the reduction is wrong

---

Problem 4: Half 3-SAT Satisfiability [25 points]

Score: 8/25 points

Assessment:

Approach: For each original clause Cᵢ = (aᵢ ∨ bᵢ ∨ cᵢ), the student adds three "negation" unit clauses (¬aᵢ), (¬bᵢ), (¬cᵢ), creating 4m total clauses. They then attempt to show that exactly 2m clauses are satisfiable iff the original formula is satisfiable.

Strengths:

Correct reduction direction (3-SAT → Half 3-SAT)
The idea of pairing each clause with clauses representing its negation shows conceptual understanding
Both proof directions are attempted with clear structure
The general analysis framework (counting satisfied clauses by cases) is appropriate

Errors/Gaps:

Format issue: Unit clauses are not valid 3-SAT clauses. Half 3-SAT specifies a "3-SAT formula," so all clauses must have exactly 3 literals. The student creates single-literal clauses.
Critical counting error: The student claims "From satisfied clauses: 0 unit clauses are satisfied." This is wrong. If clause Cᵢ is satisfied with, say, 1 literal true, then 2 of the 3 negation clauses are still satisfied (not 0). The student confuses "at least one negation is false" with "all negations are false."
The reduction is fundamentally broken: With correct counting, if a clause has j true literals (j ≥ 1), the group contributes 1 + (3−j) satisfied clauses. For j=1: 3 satisfied; j=2: 2 satisfied (exactly half); j=3: 1 satisfied. Achieving exactly 2m total requires every clause to have exactly 2 true literals — a condition that is not guaranteed by satisfiability alone.
Reverse direction also fails: Even using the student's (incorrect) formula total = 3m − 2k, setting k = m/2 yields total = 2m = half, meaning a partially-satisfying assignment (only half the clauses true) could produce a Half 3-SAT YES answer even when φ is unsatisfiable.

Detailed Feedback: The reference solution elegantly avoids these counting issues by introducing a fresh variable y and creating auxiliary clauses whose truth values are entirely determined by y. With T = (y ∨ y ∨ ¬y) (always true when y=0) and F = (y ∨ y ∨ y) (always true when y=1), the reference solution gains precise control over the clause count. Adding m copies of T and 2m copies of F creates exactly 4m clauses where the only way to satisfy exactly half is to set y=0 (making T clauses true, F clauses false) and satisfy all original clauses. The student's approach of using negation clauses cannot provide this precise control because the number of satisfied negation clauses depends on *how many* literals are true per clause, not just *whether* the clause is satisfied.

Rubric Breakdown:

Correct reduction direction: 3/5
Construction: 2/10 — creative idea but invalid (non-3-SAT clauses) and doesn't work
Forward direction proof: 2/5 — based on incorrect counting
Backward direction proof: 0/5 — the argument is both based on wrong counting and doesn't establish the claim even with its own formula
Polynomial time: 1/5 — trivially true but the reduction is wrong

---

Overall Summary

Problem	Score	Notes
1 - Efficient Recruiting	25/25	Perfect — correct construction and proof
2 - Plot Fulfillment	10/25	Missing size parameter k; always produces YES
3 - Path Selection	5/25	Single-node paths can't encode adjacency; false claim in proof
4 - Half 3-SAT	8/25	Invalid clause format, critical counting error, reduction broken
Total	48/100

General Comments:

The student demonstrates a strong command of NP-completeness reductions in Problem 1, which is correct and well-presented. However, Problems 2–4 share a common weakness: the constructions fail to encode the key constraint that makes the source problem hard. In Problem 2, the size bound k is entirely absent. In Problem 3, adjacency is not encoded because single-node paths are always disjoint. In Problem 4, the precise counting needed for "exactly half" breaks down because the construction doesn't provide sufficient control over clause satisfaction counts. A recurring pattern is that the student writes clear, well-structured proofs but doesn't verify the correctness of the underlying construction — the proofs "look right" but are built on flawed foundations. Greater attention to constructing concrete small examples and checking the reduction on them would help catch these errors before writing the proof.

Total: 48/100

writeup.md

diff --git a/writeup.md b/writeup.md
index 6069765..5e2e2bc 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,172 @@
-# COMP382 Homework 7
+# COMP382 Homework 7: NP-Completeness Reductions
 
-## Student Responses
+## Problem 1: Efficient Recruiting [25 points]
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+**Claim:** Vertex Cover ≤ₚ Efficient Recruiting
 
-[Your solutions here]
+**Reduction:**
 
+Given a Vertex Cover instance consisting of:
+- Graph G = (V, E) where |V| = n and |E| = m
+- Integer k (determine if there is a vertex cover of size ≤ k)
+
+We construct an Efficient Recruiting instance as follows:
+
+**Construction:**
+- **Sports:** Create one sport for each edge in E. We have m sports total.
+- **Counselors:** Create one counselor for each vertex in V. We have n counselors total.
+- **Qualifications:** For each edge e = (u, v) ∈ E, the counselors corresponding to vertices u and v are qualified for sport e (these are the only two qualified).
+- **Threshold:** k (same as the vertex cover threshold)
+
+**Proof of Correctness:**
+
+**Direction 1 (YES for VC → YES for ER):**
+Suppose there exists a vertex cover S ⊆ V with |S| ≤ k. By definition of vertex cover, every edge has at least one endpoint in S. Therefore, for each sport (corresponding to edge e = (u,v)), at least one of the two qualified counselors (corresponding to u or v) is in S. If we hire exactly the counselors in S, all m sports have at least one qualified counselor, and we've hired at most k counselors.
+
+**Direction 2 (NO for VC → NO for ER):**
+Conversely, suppose there is no vertex cover of size ≤ k. If we could hire at most k counselors to cover all m sports, then for each sport (edge e = (u,v)), at least one of the corresponding counselors is hired. This means the set of hired counselors is a vertex cover of G. But this contradicts our assumption that no vertex cover of size ≤ k exists. Therefore, it's impossible to hire ≤ k counselors to cover all sports.
+
+**Conclusion:** The reduction is polynomial time and preserves the answer. Therefore, Vertex Cover ≤ₚ Efficient Recruiting. ✓
+
+---
+
+## Problem 2: Plot Fulfillment [25 points]
+
+**Claim:** Hitting Set ≤ₚ Plot Fulfillment
+
+**Reduction:**
+
+Given a Hitting Set instance consisting of:
+- Universe U = {u₁, u₂, ..., u_ℓ}
+- Sets S₁, S₂, ..., S_n where each Sᵢ ⊆ U
+- Integer k (determine if there is a hitting set of size ≤ k)
+
+We construct a Plot Fulfillment instance (hypertext) as follows:
+
+**Construction:**
+- **Pages:** Create pages {s, c₁, c₂, ..., c_{n-1}, t} ∪ U
+  - s = start page
+  - t = end page
+  - c₁, ..., c_{n-1} = checkpoint pages
+  - U itself provides the remaining pages
+
+- **Thematic Elements:** For i = 1 to n, let Tᵢ = Sᵢ
+
+- **Links (directed graph edges):**
+  - From s to each element u ∈ S₁
+  - For i = 1 to n-1:
+    - From each u ∈ Sᵢ to checkpoint c_i
+    - From checkpoint c_i to each element in S_{i+1}
+  - From each u ∈ S_n to t
+
+**Key structure:** This creates a "chain" where any trail from s to t must pass through sequential sets, selecting at least one element from each set along the way.
+
+**Proof of Correctness:**
+
+The graph structure forces any path from s to t to have the form:
+```
+s → p₁ → c₁ → p₂ → c₂ → ... → c_{n-1} → p_n → t
+```
+where pᵢ ∈ Sᵢ for each i = 1 to n.
+
+**Direction 1 (YES for HS → YES for PF):**
+If there exists a hitting set H (which hits all sets), then for each i, there exists an element hᵢ ∈ H ∩ Sᵢ. We can construct the trail:
+```
+s → h₁ → c₁ → h₂ → c₂ → ... → c_{n-1} → h_n → t
+```
+This trail connects s to t and contains at least one page from each thematic element Tᵢ.
+
+**Direction 2 (YES for PF → YES for HS):**
+If there exists a trail from s to t containing pages from all thematic elements, then by the graph structure, the trail must be of the form above with pᵢ ∈ Sᵢ. The set {p₁, p₂, ..., p_n} forms a hitting set: it contains at least one element from each set Sᵢ.
+
+**Conclusion:** The reduction is polynomial time and preserves YES/NO answers. Therefore, Hitting Set ≤ₚ Plot Fulfillment. ✓
+
+---
+
+## Problem 3: Path Selection [25 points]
+
+**Claim:** Independent Set ≤ₚ Path Selection
+
+**Reduction:**
+
+Given an Independent Set instance consisting of:
+- Graph G = (V, E) with V = {v₁, v₂, ..., v_n}
+- Integer k (determine if there is an independent set of size ≤ k)
+
+We construct a Path Selection instance as follows:
+
+**Construction:**
+- **Graph:** Use the same graph G = (V, E)
+- **Path requests:** For each vertex vᵢ ∈ V, define path request Pᵢ as a single-node path: Pᵢ = (vᵢ)
+- **Threshold:** k (determine if we can select at least k node-disjoint paths)
+
+**Proof of Correctness:**
+
+**Direction 1 (YES for IS → YES for PS):**
+Suppose there exists an independent set S ⊆ V with |S| ≤ k such that no two vertices in S are adjacent. Consider the set of paths {Pᵢ : vᵢ ∈ S}. Each path is a single node, so two paths share a node if and only if they correspond to the same vertex. Since all vertices in S are distinct, these k paths are node-disjoint. Therefore, we can select at least k node-disjoint paths.
+
+**Direction 2 (YES for PS → YES for IS):**
+Conversely, suppose we can select at least k paths that are node-disjoint. Since each path Pᵢ consists only of the single node vᵢ, k node-disjoint paths correspond to k distinct vertices. Moreover, these vertices cannot have edges between them (as an edge e = (u,v) would mean paths Pᵤ and Pᵥ both contain nodes u and v, violating node-disjointness). Thus, these k vertices form an independent set.
+
+**Conclusion:** The reduction is polynomial time and preserves YES/NO answers. Therefore, Independent Set ≤ₚ Path Selection. ✓
+
+---
+
+## Problem 4: Half 3-SAT Satisfiability [25 points]
+
+**Claim:** 3-SAT ≤ₚ Half 3-SAT Satisfiability
+
+**Reduction:**
+
+Given a 3-SAT instance consisting of:
+- Variables x₁, x₂, ..., x_n
+- m clauses C₁, C₂, ..., C_m where each Cᵢ is a disjunction of exactly three literals
+
+We construct a Half 3-SAT instance as follows:
+
+**Construction:**
+
+For each clause Cᵢ = (lᵢ₁ ∨ lᵢ₂ ∨ lᵢ₃) in the original formula:
+
+1. **Include the original clause:** Add Cᵢ to the new formula
+2. **Include three negation unit clauses:** If Cᵢ = (aᵢ ∨ bᵢ ∨ cᵢ), add the three clauses:
+   - (¬aᵢ)
+   - (¬bᵢ)
+   - (¬cᵢ)
+
+   These three clauses together represent the negation of Cᵢ: namely, ¬Cᵢ = (¬aᵢ ∧ ¬bᵢ ∧ ¬cᵢ)
+
+**Total clauses in new formula:** m + 3m = 4m clauses
+
+**Question:** Does there exist an assignment satisfying exactly 2m out of 4m clauses?
+
+**Proof of Correctness:**
+
+We analyze how many clauses are satisfied based on how many original clauses are satisfied.
+
+Suppose an assignment satisfies exactly k of the original m clauses. Then:
+- **Original clauses satisfied:** exactly k
+- **Unit clauses satisfied:** For the 3m unit clauses:
+  - If original clause Cᵢ is satisfied, then at least one of aᵢ, bᵢ, cᵢ is true, so at least one of the negations ¬aᵢ, ¬bᵢ, ¬cᵢ is false. This means at most 2 of the 3 corresponding unit clauses are satisfied.
+  - If original clause Cᵢ is unsatisfied, then all of aᵢ, bᵢ, cᵢ are false, so all of ¬aᵢ, ¬bᵢ, ¬cᵢ are true. This means all 3 corresponding unit clauses are satisfied.
+
+  If k clauses are satisfied and m-k are unsatisfied:
+  - From unsatisfied clauses: 3(m-k) unit clauses are satisfied
+  - From satisfied clauses: 0 unit clauses are satisfied (since each satisfied clause makes at least one unit clause false)
+  - **Total unit clauses satisfied:** 3(m-k)
+
+**Total clauses satisfied:** k + 3(m-k) = k + 3m - 3k = 3m - 2k
+
+**Direction 1 (YES for 3-SAT → YES for Half 3-SAT):**
+If the original 3-SAT instance is satisfiable, there exists an assignment satisfying all m original clauses (k = m). Under this assignment:
+- Total satisfied clauses = 3m - 2m = m
+- This is exactly half of 4m ✓
+
+**Direction 2 (NO for 3-SAT → NO for Half 3-SAT):**
+If the original 3-SAT instance is unsatisfiable, then k < m for any assignment. Under any assignment where k < m:
+- Total satisfied clauses = 3m - 2k > 3m - 2m = m
+- This is MORE than half of 4m, so exactly m clauses cannot be satisfied
+
+Therefore, exactly 2m clauses can be satisfied if and only if all original clauses are satisfiable.
+
+**Conclusion:** The reduction is polynomial time and preserves YES/NO answers. Therefore, 3-SAT ≤ₚ Half 3-SAT Satisfiability. ✓

Agent Work: Homework7

COMP 382: Reasoning about Algorithms

Homework 7

Problem 1: Efficient Recruiting [25 points]

Problem 2: Plot Fulfillment [25 points]

Problem 3: Path Selection [25 points]

Problem 4: Half 3-SAT Satisfiability [25 points]

COMP382 Homework 7: NP-Completeness Reductions

Problem 1: Efficient Recruiting [25 points]

Problem 2: Plot Fulfillment [25 points]

Problem 3: Path Selection [25 points]

Problem 4: Half 3-SAT Satisfiability [25 points]

Problem 1: Efficient Recruiting [25 points]

Score: 25/25 points

Assessment:

Rubric Breakdown:

Problem 2: Plot Fulfillment [25 points]

Score: 10/25 points

Assessment:

Rubric Breakdown:

Problem 3: Path Selection [25 points]

Score: 5/25 points

Assessment:

Rubric Breakdown:

Problem 4: Half 3-SAT Satisfiability [25 points]

Score: 8/25 points

Assessment:

Rubric Breakdown:

Overall Summary

General Comments:

Sub-Model Usage