📚 L9: Reductions & Intractability

Lecture Goal

Understand how reductions formalize “problem A is no harder than problem B”, use reductions to prove hardness, and see the chain that connects 3-SAT, Independent Set, Vertex Cover, and Set Cover.

The Big Picture

Reductions are the universal language of hardness. Instead of proving each problem hard from scratch, we show a known-hard problem reduces to it — and hardness “flows” through the reduction chain. This is how we know thousands of problems are all equivalent in difficulty to 3-SAT.

1. What is a Reduction?

🤔 The Core Problem

Instead of learning a new algorithm for every problem, can we transform one problem into another we already know how to solve?

💡 The Reduction Concept

A reduction is a way to solve problem $A$ by transforming it into a problem $B$ that you already know how to solve.

flowchart LR
    A["Instance α<br/>(Problem A)"] -->|"Convert"| B["Instance β<br/>(Problem B)"]
    B -->|"Solve B"| S["Solution B(β)"]
    S -->|"Translate back"| R["Solution A(α) ✅"]

    style A fill:#e1f5fe
    style B fill:#fff9c4
    style S fill:#c8e6c9
    style R fill:#c8e6c9

Formally, to reduce $A$ to $B$ :

Take an instance $α$ of problem $A$
Convert $α$ into an instance $β$ of problem $B$ (this is the reduction step)
Solve $B$ on $β$
Translate $B$ ‘s answer back into an answer for $A$

We write this as: $A \leq_{P} B$ , read as “A reduces to B” or “A is no harder than B”.

📖 Key Terminology

Term	Definition
Instance	A specific input to a problem (sometimes called “encoding”)
Reduction	A transformation from instances of $A$ to instances of $B$
$A \leq_{P} B$	” $A$ reduces to $B$ ” — solving $B$ gives us a way to solve $A$

💡 Warm-Up Example: T-SUM reduces to 0-SUM

0-SUM: Given array $A$ , find $i, j$ such that $A [i] + A [j] = 0$
T-SUM: Given array $B$ and number $T$ , find $i, j$ such that $B [i] + B [j] = T$

flowchart LR
    B["Array B, Target T<br/>(T-SUM instance)"] -->|"Define A[i] = B[i] - T/2"| A["Array A<br/>(0-SUM instance)"]
    A -->|"Solve 0-SUM"| Sol["Find i,j: A[i] + A[j] = 0"]
    Sol -->|"Same i,j"| Ans["B[i] + B[j] = T ✅"]

    style B fill:#e1f5fe
    style A fill:#fff9c4
    style Sol fill:#c8e6c9

Reduction: Given $B$ for T-SUM, define $A [i] = B [i] - T /2$ .

Then $A [i] + A [j] = 0 ⟺ B [i] + B [j] = T$ . ✅

⚠️ Common Pitfalls

Pitfall 1: Confusing the direction of the reduction

$A \leq_{P} B$ means you are solving A using B. It does NOT mean $B$ is easier than $A$ — it means $B$ is at least as hard as $A$ . Students often read the arrow backwards!

Pitfall 2: Forgetting the translation step

You need both directions: converting $α \to β$ AND converting $B (β) \to A (α)$ . Forgetting the back-translation is a common error in proofs.

❓ Mock Exam Questions

Q1: Reduction Direction

If we reduce Problem A to Problem B, which problem’s algorithm do we use?

Answer

Answer: We use Problem B’s algorithm

$A \leq_{P} B$ means we transform A-instances into B-instances and solve using B’s algorithm.

Q2: Arrow Meaning

What does $A \leq_{P} B$ mean?

Answer

Answer: A is no harder than B (or equivalently, B is at least as hard as A)

The arrow points from easier to harder. If B is solvable, so is A.

2. p(n)-Time Reductions & Running Time Composition

🧠 Core Concept

A $p (n)$ -time reduction from $A$ to $B$ means:

The conversion $α \to β$ runs in $p (n)$ time
The back-translation $B (β) \to A (α)$ runs in $p (n)$ time

where $n$ is the size of the input $α$ (NOT the size of $β$ ‘s output).

flowchart TD
    subgraph Reduction ["Reduction Pipeline"]
        A["Input α (size n)"] -->|"Convert<br/>O(p(n))"| B["Instance β<br/>(size O(p(n)))"]
        B -->|"Solve B<br/>T(O(p(n)))"| S["Solution B(β)"]
        S -->|"Translate back<br/>O(p(n))"| R["Solution A(α)"]
    end

    Total["Total Time: T(O(p(n))) + O(p(n))"]

    style Reduction fill:#e1f5fe
    style Total fill:#c8e6c9

📐 Running Time Composition

If there is a $p (n)$ -time reduction from $A$ to $B$ , and $B$ has a $T (n)$ -time algorithm, then $A$ can be solved in:

$T (O (p (n))) + O (p (n)) time$

Why? The instance $β$ has size $O (p (n))$ , so solving $B$ on it takes $T (O (p (n)))$ time. Add the $O (p (n))$ for conversion and back-translation.

📖 Key Terminology

Term	Definition
$p (n)$ -time reduction	Reduction where both conversion and back-translation run in $p (n)$ time
Input size $n$	The size of the original instance $α$ — not the size of $β$
Running Time Composition	How to combine reduction cost and $B$ -solver cost to get total runtime for $A$

⚠️ Common Pitfalls

Confusing $n$ (size of $α$ ) with $∣ β ∣$ (size of constructed instance)

In the MAT-MULTI → MAT-SQR example: the input size $n = N^{2}$ (number of entries in two $N \times N$ matrices). The conversion constructs a $2 N \times 2 N$ matrix — $O (N^{2}) = O (n)$ work. So it’s an $O (n)$ -time reduction, not $O (N)$ !

3. Polynomial-Time Reductions & Pseudo-Polynomial Algorithms

🧠 Core Concept

Definition: $A \leq_{P} B$ (polynomial-time reduction) if there is a $p (n)$ -time reduction from $A$ to $B$ where $p (n) = O (n^{c})$ for some constant $c$ .

flowchart LR
    subgraph Implications ["Key Implications"]
        I1["A ≤_P B and B ∈ P<br/>⇒ A ∈ P"]
        I2["A ≤_P B and A hard<br/>⇒ B hard"]
    end

    Hard["Hard Problem A"] -->|"≤_P"| B["Problem B"]
    Hard --> I2
    B --> I1

    style I1 fill:#c8e6c9
    style I2 fill:#ffccbc
    style Hard fill:#ff9999

Key implication: $A \leq_{P} B and B solvable in poly-time ⟹ A solvable in poly-time$

Contrapositive (crucial for hardness!): $A \leq_{P} B and A is hard ⟹ B is hard$

Think of it like a disease spreading upward in difficulty: if $A$ is hard and $A$ reduces to $B$ , then $B$ “inherits” the hardness of $A$ . 🦠

Why polynomial time? The notion is robust: multiplying two polynomials gives another polynomial. So chaining reductions $A \leq_{P} B \leq_{P} C$ still gives $A \leq_{P} C$ .

📊 Pseudo-Polynomial Algorithms

An algorithm is pseudo-polynomial if it runs in time polynomial in the numeric value of the input, but exponential in the length (number of bits) of the input.

flowchart LR
    subgraph KNAPSACK ["KNAPSACK Example"]
        DP["DP runs in O(nW)"]
        Input["Input: O(n log W) bits"]
        W["W = O(2^(log W))"]
    end

    DP -->|"Polynomial in W"| Pseudo["Pseudo-polynomial ❌"]
    Input -->|"True input size"| Exp["O(nW) = O(n · 2^(log W))<br/>Exponential!"]

    style Pseudo fill:#ffccbc
    style Exp fill:#ff9999

Classic example: Dynamic programming for KNAPSACK runs in $O (nW)$ .

The input size is $O (n lo g W + lo g W)$ bits
But $W$ can be as large as $2^{(number of bits for W)}$
So $O (nW)$ is exponential in the input length → pseudo-polynomial, NOT truly polynomial ❌

Compare to FRACTIONAL KNAPSACK with $O (n lo g n)$ : this IS polynomial ✅

📖 Key Terminology

Term	Definition
$A \leq_{P} B$	$A$ polynomial-time reduces to $B$
Polynomial-time algorithm	Runs in $O (n^{c})$ for some constant $c$ , where $n$ = input encoding length
Pseudo-polynomial	Polynomial in the numeric value but exponential in the bit length
Tractable	Solvable in polynomial time
Intractable	No known polynomial-time algorithm (and strong evidence none exists)

⚠️ Common Pitfalls

Thinking $O (nW)$ is polynomial for KNAPSACK

$W$ is encoded in $O (lo g W)$ bits. So the actual input size is $n_{bi t s} = O (lo g W)$ , meaning $W = O (2^{n_{bi t s}})$ . The runtime $O (nW) = O (n \cdot 2^{n_{bi t s}})$ is exponential! Always measure polynomial-ness against the encoding length, not the numeric value.

Believing $A \leq_{P} B$ and $A$ poly-time $\Rightarrow$ $B$ poly-time

This is FALSE. The implication only goes the other way: $B$ poly-time $\Rightarrow$ $A$ poly-time. And: $A$ hard $\Rightarrow$ $B$ hard.

❓ Mock Exam Questions

Q3: Implication Direction

If $A \leq_{P} B$ and $A$ can be solved in polynomial time, what can we conclude?

Answer

Answer: Nothing about B’s complexity

The reduction only tells us: “if B is easy, then A is easy” (and contrapositively: “if A is hard, then B is hard”). It says nothing about B when A is easy.

Q4: Pseudo-polynomial Classification

The KNAPSACK DP runs in $O (nW)$ time. Input encoded in $O (n lo g W)$ bits. What is this?

Answer

Answer: Pseudo-polynomial

It’s polynomial in the numeric value $W$ , but $W = 2^{(bits for W)}$ , making it exponential in the actual input length.

4. Decision Problems vs Optimisation Problems

🧠 Core Concept

To compare problem hardness uniformly, we use a common language: decision problems.

flowchart LR
    subgraph Optimisation ["Optimisation Problem"]
        Opt["Find the BEST solution"]
        Val["Output: A value/solution"]
    end

    subgraph Decision ["Decision Problem"]
        Dec["Is there a solution<br/>with value ≥/≤ k?"]
        Ans["Output: YES or NO"]
    end

    Opt -->|"Add threshold k"| Dec
    Dec -->|"If YES for optimal k,<br/>you found the optimum"| Opt

    style Decision fill:#c8e6c9

Type	Output	Example
Optimisation	A value/solution	”What is the shortest path from $u$ to $v$ ?”
Decision	YES or NO	”Is there a path from $u$ to $v$ of length $\leq k$ ?”

Conversion recipe: Given an optimisation problem, create a decision version by introducing a threshold $k$ and asking “is there a solution with value $\leq k$ ?” (for minimisation) or ” $\geq k$ ?” (for maximisation).

Why does this work for hardness?
The decision version is no harder than the optimisation version:

If you can solve optimisation, just check if the optimal value satisfies the threshold.
So: if the decision version is hard → the optimisation version is also hard.

📖 Key Terminology

Term	Definition
Decision problem	Maps an instance to {YES, NO}
YES-instance	An input for which the answer is YES
NO-instance	An input for which the answer is NO
Threshold $k$	Parameter added to convert optimisation to decision

⚠️ Common Pitfalls

Thinking the decision problem is always strictly easier

Decision $\leq_{P}$ Optimisation (decision is no harder). But in many cases they are equivalent in hardness — if you can solve the decision version for all $k$ , you can binary search for the optimum.

5. Reductions Between Decision Problems

🧠 Core Concept

For decision problems, a poly-time reduction $A \leq_{P} B$ is a poly-time transformation $α \mapsto β$ such that:

$α is a YES-instance of A ⟺ β is a YES-instance of B$

The YES/NO answer is “copied” — no translation needed, just the if-and-only-if.

To prove a valid reduction, show three things:

✅ The transformation runs in polynomial time
✅ ( $\Rightarrow$ ) If $α$ is a YES-instance of $A$ , then $β$ is a YES-instance of $B$
✅ ( $\Leftarrow$ ) If $β$ is a YES-instance of $B$ , then $α$ is a YES-instance of $A$

Both directions of the if-and-only-if must be proved! 🔁

⚠️ Common Pitfalls

Proving only one direction of the iff

Many students prove ( $\Rightarrow$ ) but forget ( $\Leftarrow$ ), or vice versa. Both are required and examiners will look for both.

Confusing $A \leq_{P} B$ with $B \leq_{P} A$

These are very different statements! $A \leq_{P} B$ means ” $A$ is no harder than $B$ .” Always be explicit about which direction you’re reducing.

6. The Problem Zoo

🧠 Key Problems

🕸️ INDEPENDENT-SET

Problem: Given a graph $G = (V, E)$ and integer $k$ , is there a subset $S \subseteq V$ with $∣ S ∣ \geq k$ such that no two vertices in $S$ are adjacent?

flowchart TD
    subgraph Graph ["Graph G"]
        V1["●"] --- V2["●"]
        V1 --- V3["●"]
        V2 --- V4["●"]
        V3 --- V4
        V4 --- V5["●"]
    end

    IS["Independent Set S<br/>(no edges between members)"]
    Size["|S| ≥ k?"]

    style V1 fill:#c8e6c9
    style V3 fill:#c8e6c9
    style V5 fill:#c8e6c9

Analogy: A group of people at a party where nobody knows each other — they’re “independent.” 🥳

🛡️ VERTEX-COVER

Problem: Given a graph $G = (V, E)$ and integer $k$ , is there a subset $S \subseteq V$ with $∣ S ∣ \leq k$ such that every edge has at least one endpoint in $S$ ?

Analogy: Place security cameras at $k$ intersections so that every road is watched by at least one camera. 📷

🧩 SET-COVER

Problem: Given integers $k$ , $n$ , and a collection $S$ of subsets of ${1, \dots, n}$ , are there $\leq k$ subsets in $S$ whose union is ${1, \dots, n}$ ?

Analogy: Choose $k$ radio stations so that every city is in at least one station’s broadcast range. 📻

🔮 3-SAT

flowchart LR
    subgraph Building ["Building Blocks"]
        Lit["Literal: xᵢ or x̄ᵢ"]
        Clause["Clause: (x₁ ∨ x₂ ∨ x̄₃)"]
        CNF["CNF: AND of clauses"]
    end

    Problem["Does Φ have a<br/>satisfying assignment?"]

    Lit --> Clause --> CNF --> Problem

    style Problem fill:#fff9c4

Building blocks:

Literal: A Boolean variable $x_{i}$ or its negation $\overset{x}{ˉ}_{i}$
Clause: A disjunction (OR) of literals, e.g., $(x_{1} \lor x_{2} \lor \overset{x}{ˉ}_{3})$
CNF formula: A conjunction (AND) of clauses

Problem: Given a CNF formula $Φ$ where every clause has exactly 3 literals, does $Φ$ have a satisfying truth assignment?

Analogy: Can you set switches (True/False) so that in every group of 3 switches, at least one is ON? 💡

📖 Key Terminology Summary

Problem	Input	YES iff…
INDEPENDENT-SET	$G, k$	$\exists$ subset of $\geq k$ mutually non-adjacent vertices
VERTEX-COVER	$G, k$	$\exists$ subset of $\leq k$ vertices touching all edges
SET-COVER	$n, k, S$	$\exists \leq k$ subsets whose union $= {1, \dots, n}$
3-SAT	CNF formula $Φ$	$\exists$ truth assignment satisfying all clauses

⚠️ Common Pitfalls

Confusing Independent Set and Vertex Cover

Independent Set wants vertices with NO edges between them (size $\geq k$ ). Vertex Cover wants vertices that TOUCH all edges (size $\leq k$ ). Note the complementary nature — this is exactly the key insight in their reduction!

7. The Reduction Chain

The lecture builds the following reduction chain:

flowchart LR
    SAT["3-SAT"] -->|"≤_P"| IS["INDEPENDENT-SET"]
    IS -->|"≤_P"| VC["VERTEX-COVER"]
    VC -->|"≤_P"| SC["SET-COVER"]

    Hard["All believed HARD"] --> SAT

    style SAT fill:#ff9999
    style IS fill:#ffccbc
    style VC fill:#ffccbc
    style SC fill:#ffccbc

By transitivity: $3-SAT \leq_{P} SET-COVER$ . Since 3-SAT is believed to be hard, all problems in this chain are believed to be hard! 😱

7.1 INDEPENDENT-SET $\leq_{P}$ VERTEX-COVER

flowchart LR
    subgraph KeyInsight ["Key Insight"]
        IS["S is Independent Set"]
        VC["V \\ S is Vertex Cover"]
    end

    IS <--> VC

    subgraph Reduction ["Reduction"]
        Input["(G, k) for IS"]
        Output["(G, n-k) for VC"]
    end

    Input -->|"Complement"| Output

    style KeyInsight fill:#e1f5fe

Key Insight: $S$ is an independent set in $G$ $⟺$ $V ∖ S$ is a vertex cover.

Reduction: $(G, k)$ is a YES-instance of INDEPENDENT-SET $⟺$ $(G, n - k)$ is a YES-instance of VERTEX-COVER (where $n = ∣ V ∣$ ).

Proof ( $\Rightarrow$ ):
Suppose $S$ , $∣ S ∣ \geq k$ , is an independent set. For any edge $(u, v) \in E$ : since $S$ is independent, at least one of $u, v \in / S$ , so at least one of them is in $V ∖ S$ . Thus $V ∖ S$ is a vertex cover of size $\leq n - k$ . ✅

Proof ( $\Leftarrow$ ):
Suppose $S$ , $∣ S ∣ \leq n - k$ , is a vertex cover. If $u, v \in V ∖ S$ and $(u, v) \in E$ , then neither endpoint is in $S$ , contradicting $S$ being a vertex cover. So $V ∖ S$ is an independent set of size $\geq k$ . ✅

7.2 VERTEX-COVER $\leq_{P}$ SET-COVER

flowchart TD
    subgraph Graph ["Graph G = (V, E)"]
        E1["Edge e₁"]
        E2["Edge e₂"]
        E3["..."]
    end

    subgraph SetCover ["Set Cover Instance"]
        U["Universe U = {1, 2, ..., |E|}<br/>(edge indices)"]
        Sets["For each vertex v:<br/>Sᵥ = {i : eᵢ incident on v}"]
        K["k' = k"]
    end

    Graph -->|"Edges become<br/>universe elements"| SetCover

    style Graph fill:#e1f5fe
    style SetCover fill:#fff9c4

Reduction: Given $(G, k)$ for VERTEX-COVER, construct:

Universe $U = {1, \dots, ∣ E ∣}$ (label edges $e_{1}, \dots, e_{m}$ )
For each vertex $v \in V$ : $S_{v} = {i : e_{i} is incident on v}$
Set $k^{'} = k$

Intuition: Each vertex “covers” the edges incident to it. Choosing a vertex cover of size $k$ corresponds to choosing $k$ sets that together cover all edge indices.

Proof ( $\Rightarrow$ ):
If $U \subseteq V$ is a vertex cover of size $\leq k$ , then every edge has an endpoint in $U$ , so $⋃_{u \in U} S_{u} = {1, \dots, m}$ . ✅

Proof ( $\Leftarrow$ ):
If ${S_{v_{1}}, \dots, S_{v_{t}}}$ ( $t \leq k$ ) form a set cover, then every edge index is covered, meaning every edge has an endpoint in ${v_{1}, \dots, v_{t}}$ — a vertex cover of size $\leq k$ . ✅

7.3 3-SAT $\leq_{P}$ INDEPENDENT-SET

flowchart TD
    subgraph Construction ["Construction from 3-SAT Φ with m clauses"]
        C1["Clause 1<br/>(x₁ ∨ x̄₂ ∨ x₃)"]
        C2["Clause 2<br/>(x̄₁ ∨ x₂ ∨ x₄)"]
        C3["..."]
        Cm["Clause m"]
    end

    subgraph Graph ["Independent Set Graph"]
        T1["Triangle: 3 literals<br/>per clause"]
        T2["Triangle"]
        Conflict["Conflict edges: connect<br/>xᵢ to x̄ᵢ"]
    end

    C1 --> T1
    C2 --> T2
    Construction -->|"k = m"| Graph

    style T1 fill:#fff9c4
    style T2 fill:#fff9c4
    style Conflict fill:#ff9999

Reduction: Given 3-SAT instance $Φ$ with $m$ clauses:

Create 3 vertices per clause (one per literal) — label them with the literal
Connect the 3 literals in each clause in a triangle (intra-clause edges)
Connect each literal to all occurrences of its negation in other clauses (conflict edges)
Set $k = m$ (number of clauses)

Why triangles? An independent set can pick at most 1 vertex from each triangle — forcing us to pick exactly one literal per clause to satisfy.

Why conflict edges? These prevent us from picking $x_{i}$ from one clause and $\overset{x}{ˉ}_{i}$ from another — they can’t both be true!

Proof ( $\Rightarrow$ ):
Given a satisfying assignment, pick one true literal per clause. These $m$ vertices form an independent set:

No two are in the same triangle (one per clause) ✅
No two are connected by a conflict edge (can’t have $x_{i}$ and $\overset{x}{ˉ}_{i}$ both true) ✅

Proof ( $\Leftarrow$ ):
Given an independent set $S$ of size $k = m$ : exactly one vertex from each triangle is in $S$ . Set those literals to true. This is consistent (conflict edges prevent $x_{i}$ and $\overset{x}{ˉ}_{i}$ both being chosen), and every clause is satisfied. ✅

⚠️ Common Pitfalls

3-SAT → IS: Forgetting conflict edges

Without conflict edges, you could pick $x_{1}$ from one triangle and $\overset{x}{ˉ}_{1}$ from another — a contradiction. The conflict edges are essential for correctness.

IS → VC: Thinking the complement has size exactly $n - k$

If $∣ S ∣ \geq k$ , then $∣ V ∖ S ∣ \leq n - k$ . The inequality goes the right way — don’t flip it!

VC → Set Cover: The universe is the set of EDGES, not vertices

Students often confuse what the universe $U$ represents. It encodes edges, not vertices.

8. NP-Completeness (Preview)

🧠 Core Concept

All the problems seen (3-SAT, INDEPENDENT-SET, VERTEX-COVER, SET-COVER, KNAPSACK, etc.) are NP-complete:

flowchart TD
    subgraph NPC ["NP-Complete Problems"]
        SAT["3-SAT"]
        IS["INDEPENDENT-SET"]
        VC["VERTEX-COVER"]
        SC["SET-COVER"]
        KS["KNAPSACK"]
        etc["...thousands more"]
    end

    Implication["If ANY ONE has a poly-time algorithm,<br/>then ALL of them do<br/>⇒ P = NP"]

    SAT --> Implication

    style NPC fill:#ffccbc
    style Implication fill:#fff9c4

If any one of these NP-complete problems has a polynomial-time algorithm, then all of them do — and we would have $P = NP$ .

No polynomial-time algorithm is known for any of them. Most computer scientists believe $P \neq = NP$ , meaning these problems are genuinely intractable. 💀

The web of reductions you’ve seen (Dick Karp’s famous 1972 paper!) shows that these seemingly unrelated problems from graph theory, logic, and combinatorics are all equivalent in hardness.

🔗 Connections

📚 Lecture	🔗 Connection
L10	Using reductions to prove NP-completeness

The Key Insight

Reductions let us stand on the shoulders of giants. We don’t need to prove hardness from scratch — we just show our problem is “at least as hard” as a known-hard problem. The entire NP-completeness web rests on this powerful idea. 🕸️

9. Mock Exam Questions

📝 Multiple Choice

Q1: Reduction Implication

Suppose $A \leq_{P} B$ . Which of the following statements is definitely true?

Answer

Answer: (b) If $B$ can be solved in polynomial time, then so can $A$ .

$A \leq_{P} B$ means “if $B$ is easy, then $A$ is easy.” It does NOT imply the reverse.

Q2: KNAPSACK Classification

The dynamic programming algorithm for KNAPSACK runs in $O (nW)$ time. The input is encoded using $O (n lo g W + lo g W)$ bits. Which correctly classifies this algorithm?

Answer

Answer: (c) Pseudo-polynomial, because it is polynomial in the numeric value of $W$ but exponential in the bit length of $W$ .

$W = O (2^{l o g W})$ , so $O (nW) = O (n \cdot 2^{(bits for W)})$ is exponential in the encoding length.

Q3: Conflict Edges Purpose

In the 3-SAT $\leq_{P}$ INDEPENDENT-SET reduction, what is the purpose of connecting a literal vertex to its negation vertex in another clause?

Answer

Answer: (b) To ensure we don’t simultaneously set a variable to both TRUE and FALSE.

Intra-clause triangles enforce “at most one per clause.” Conflict edges enforce consistency of the truth assignment across clauses.

✍️ Open-Ended Practice Problems

P1: SUBSET-SUM ≤_P ZERO-SUBSET-SUM

Let SUBSET-SUM be: Given set $S = {s_{1}, \dots, s_{n}}$ and target $T$ , does there exist a subset $S^{'} \subseteq S$ such that $\sum_{i \in S^{'}} s_{i} = T$ ?

Define ZERO-SUBSET-SUM: Given a set of integers $S = {s_{1}, \dots, s_{n}}$ , does there exist a non-empty subset $S^{'} \subseteq S$ such that $\sum_{i \in S^{'}} s_{i} = 0$ ?

Show that SUBSET-SUM $\leq_{P}$ ZERO-SUBSET-SUM. Clearly describe the reduction and prove correctness in both directions.

Answer

Reduction: Given $(S, T)$ for SUBSET-SUM, construct $S^{'} = S \cup {- T}$ for ZERO-SUBSET-SUM.

Runtime: $O (1)$ — clearly polynomial time. ✅

Correctness ( $\Rightarrow$ ): If $(S, T)$ is YES, there exists $S^{*} \subseteq S$ with $\sum_{i \in S^{*}} s_{i} = T$ . Then $S^{*} \cup {- T} \subseteq S^{'}$ has sum $T - T = 0$ . ✅

Correctness ( $\Leftarrow$ ): If $S^{'}$ is YES for ZERO-SUBSET-SUM, there exists non-empty $S^{**} \subseteq S^{'}$ with sum 0.

If $- T \in S^{**}$ : Then $S^{*} = S^{**} ∖ {- T} \subseteq S$ has sum $T$ . ✅

If $- T \in / S^{**}$ : Then $S^{**} \subseteq S$ has sum 0, meaning $T = 0$ (trivially YES for SUBSET-SUM). ✅

P2: INDEPENDENT-SET → VERTEX-COVER

(a) Given a graph $G$ with 8 vertices and an independent set $S$ of size 5, what is the minimum size of a vertex cover guaranteed by the reduction?

(b) Suppose someone claims: “If $A \leq_{P} B$ and $A$ can be solved in polynomial time, then $B$ can be solved in polynomial time.” Is this TRUE or FALSE? Justify.

(c) In the VERTEX-COVER $\leq_{P}$ SET-COVER reduction, what does the universe $U$ represent, and why is it defined this way?

Answer

(a) Vertex cover size $\leq n - k = 8 - 5 = 3$ . The complement $V ∖ S$ has size at most 3 and forms a vertex cover.

(b) FALSE. $A \leq_{P} B$ means “if $B$ is easy, then $A$ is easy.” It says nothing about what happens when $A$ is easy. Counterexample: Let $A$ be any trivial problem (solvable in $O (1)$ ), and $B$ be any hard problem. We can reduce $A$ to $B$ , but $B$ might not be polynomial-time solvable.

(c) The universe $U = {1, 2, \dots, ∣ E ∣}$ represents the edges of the graph $G$ . Each edge is labeled $e_{1}, \dots, e_{m}$ . A vertex cover must “touch” every edge. By encoding edges as universe elements, “covering the universe” corresponds exactly to “every edge being touched by some chosen vertex.”

Quartz 4

Explorer

L9

📚 L9: Reductions & Intractability

1. What is a Reduction?

🤔 The Core Problem

💡 The Reduction Concept

📖 Key Terminology

💡 Warm-Up Example: T-SUM reduces to 0-SUM

⚠️ Common Pitfalls

❓ Mock Exam Questions

2. p(n)-Time Reductions & Running Time Composition

🧠 Core Concept

📐 Running Time Composition

📖 Key Terminology

⚠️ Common Pitfalls

3. Polynomial-Time Reductions & Pseudo-Polynomial Algorithms

🧠 Core Concept

📊 Pseudo-Polynomial Algorithms

📖 Key Terminology

⚠️ Common Pitfalls

❓ Mock Exam Questions

4. Decision Problems vs Optimisation Problems

🧠 Core Concept

📖 Key Terminology

⚠️ Common Pitfalls

5. Reductions Between Decision Problems

🧠 Core Concept

⚠️ Common Pitfalls

6. The Problem Zoo

🧠 Key Problems

🕸️ INDEPENDENT-SET

🛡️ VERTEX-COVER

🧩 SET-COVER

🔮 3-SAT

📖 Key Terminology Summary

⚠️ Common Pitfalls

7. The Reduction Chain

7.1 INDEPENDENT-SET ≤P​ VERTEX-COVER

7.2 VERTEX-COVER ≤P​ SET-COVER

7.3 3-SAT ≤P​ INDEPENDENT-SET

⚠️ Common Pitfalls

8. NP-Completeness (Preview)

🧠 Core Concept

🔗 Connections

9. Mock Exam Questions

📝 Multiple Choice

✍️ Open-Ended Practice Problems

Graph View

Table of Contents

7.1 INDEPENDENT-SET $\leq_{P}$ VERTEX-COVER

7.2 VERTEX-COVER $\leq_{P}$ SET-COVER

7.3 3-SAT $\leq_{P}$ INDEPENDENT-SET