More Reductions for NP Problems

More Reductions for NP Problems

Nabil Mustafa

Computational Complexity

Reductions From Last Time

So far, we have shown the following problems NP complete:

SAT , 3-CNF SAT, INDSET , CLIQUE , VERTEX-COVER , HITTING-SET , INTEGER-PROGRAMMING

IS SAT

3-SAT

IP HS

VC

CL

2 / 177

HAMILTONIAN

Claim

HAMILTONIAN : Given a directed graph G = (V, E), does G have a Hamiltonian path?

The Hamiltonian path problem (HAMILTONIAN ) is NP complete.

Review: Hamiltonian path visits each vertex in G exactly once Computationally very different from Eulerian paths

Note that HAMILTONIAN is in NP We reduce 3-CNF SAT to HAMILTONIAN

I For a fixed 3-CNF SAT formula, show that it can be transformed into a graph whose Hamiltonian path will give us the assignments for SAT.

HAMILTONIAN

Claim

HAMILTONIAN : Given a directed graph G = (V, E), does G have a Hamiltonian path?

The Hamiltonian path problem (HAMILTONIAN ) is NP complete.

Review: Hamiltonian path visits each vertex in G exactly once

Computationally very different from Eulerian paths Note that HAMILTONIAN is in NP

We reduce 3-CNF SAT to HAMILTONIAN

I For a fixed 3-CNF SAT formula, show that it can be transformed into a graph whose Hamiltonian path will give us the assignments for SAT.

4 / 177

HAMILTONIAN

Claim

HAMILTONIAN : Given a directed graph G = (V, E), does G have a Hamiltonian path?

The Hamiltonian path problem (HAMILTONIAN ) is NP complete.

Review: Hamiltonian path visits each vertex in G exactly once Computationally very different from Eulerian paths

Note that HAMILTONIAN is in NP We reduce 3-CNF SAT to HAMILTONIAN

I For a fixed 3-CNF SAT formula, show that it can be transformed into a graph whose Hamiltonian path will give us the assignments for SAT.

HAMILTONIAN

Claim

HAMILTONIAN : Given a directed graph G = (V, E), does G have a Hamiltonian path?

The Hamiltonian path problem (HAMILTONIAN ) is NP complete.

Review: Hamiltonian path visits each vertex in G exactly once Computationally very different from Eulerian paths

Note that HAMILTONIAN is in NP

We reduce 3-CNF SAT to HAMILTONIAN

I For a fixed 3-CNF SAT formula, show that it can be transformed into a graph whose Hamiltonian path will give us the assignments for SAT.

6 / 177

HAMILTONIAN

Claim

HAMILTONIAN : Given a directed graph G = (V, E), does G have a Hamiltonian path?

The Hamiltonian path problem (HAMILTONIAN ) is NP complete.

Review: Hamiltonian path visits each vertex in G exactly once Computationally very different from Eulerian paths

Note that HAMILTONIAN is in NP We reduce 3-CNF SAT to HAMILTONIAN

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses. Each x_i will correspond to a path (chain) of 6m vertices If we are at the first (or end) vertex, only one path to follow

x

8 / 177

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses. Each x_i will correspond to a path (chain) of 6m vertices If we are at the first (or end) vertex, only one path to follow

x

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses.

Each x_i will correspond to a path (chain) of 6m vertices If we are at the first (or end) vertex, only one path to follow

x

10 / 177

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses.

Each x_i will correspond to a path (chain) of 6m vertices

If we are at the first (or end) vertex, only one path to follow

x

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses.

Each x_i will correspond to a path (chain) of 6m vertices

If we are at the first (or end) vertex, only one path to follow

x

12 / 177

Reduction Sketch

φ = C1∧ C2∧ . . . ∧ Cm, n variables, Ci = (x₁ⁱ ∨ x2ⁱ ∨ x3ⁱ)

Givenφ, have to construct a graph G such that G has a Hamiltonian path iff φ is satisfiable.

We first define the mapping of variables, and then the clauses.

Each x_i will correspond to a path (chain) of 6m vertices If we are at the first (or end) vertex, only one path to follow

x

Add a start vertex v_start which has

I no incoming edges.

I an outgoing edge to the first vertex of x1chain.

I an outgoing edge to the last vertex of x1 chain.

x1

x2

vstart

xn−1

xn

14 / 177

Add a start vertex v_start which has

I no incoming edges.

I an outgoing edge to the first vertex of x1chain.

I an outgoing edge to the last vertex of x1 chain.

x1

x2

vstart

xn−1

xn

Add a start vertex v_start which has

I no incoming edges.

I an outgoing edge to the first vertex of x1chain.

I an outgoing edge to the last vertex of x1 chain.

x1

x2

vstart

xn−1

xn

16 / 177

Add a start vertex v_start which has

I no incoming edges.

I an outgoing edge to the first vertex of x1chain.

I an outgoing edge to the last vertex of x1 chain.

x1

x2

vstart

xn−1

xn

Add a start vertex v_start which has

I no incoming edges.

I an outgoing edge to the first vertex of x1chain.

I an outgoing edge to the last vertex of x1 chain.

x1

x2

vstart

xn−1

xn

18 / 177

Add an end vertex v_end which has

I no outgoing edges.

I an incoming edge from the first vertex of xnchain.

I an incoming edge from the last vertex of xn chain.

x1

x2

vend

xn−1

xn

vstart

Add an end vertex v_end which has

I no outgoing edges.

I an incoming edge from the first vertex of xnchain.

I an incoming edge from the last vertex of xn chain.

x1

x2

vend

xn−1

xn

vstart

20 / 177

Add an end vertex v_end which has

I no outgoing edges.

I an incoming edge from the first vertex of xnchain.

I an incoming edge from the last vertex of xn chain.

x1

x2

vend

xn−1

xn

vstart

Add an end vertex v_end which has

I no outgoing edges.

I an incoming edge from the first vertex of xnchain.

I an incoming edge from the last vertex of xn chain.

x1

x2

vend

xn−1

xn

vstart

22 / 177

Add an end vertex v_end which has

I no outgoing edges.

I an incoming edge from the first vertex of xnchain.

I an incoming edge from the last vertex of xn chain.

x1

x2

xn−1

xn

vstart

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

24 / 177

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1

I an outgoing edge to the last vertex of chain xi +1

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

26 / 177

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

x1

x2

xn−1

xn

vstart

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

x1

x2

vend

xn−1

xn

vstart

28 / 177

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

x1

x2

xn−1

xn

vstart

From the first and last vertex of each chain x_i, add

I an outgoing edge to the first vertex of chain xi +1 I an outgoing edge to the last vertex of chain xi +1

x1

x2

vend

xn−1

xn

vstart

30 / 177

Construction Properties

x1

x2

xn−1

xn

vstart

Construction Properties

Any Hamiltonian path has to start at v_start

x1

x2

vend

xn−1

xn

vstart

32 / 177

Construction Properties

Any Hamiltonian path has to end at v_end

x1

x2

xn−1

xn

vstart

Construction Properties

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

x1

x2

vend

xn−1

xn

vstart

34 / 177

Construction Properties

For each chain, only two ways of traversing it.

I Left-to-right means xi = 1, right-to-left means xi = 0

x1

x2

xn−1

xn

vstart

Construction Properties

Each assignment of variables corresponds to a unique Hamiltonian path.

x1

x2

vend

xn−1

xn

vstart

36 / 177

Construction Properties

Each Hamiltonian path corresponds to a unique variable assignment.

x1

x2

xn−1

xn

vstart

Construction Properties

So far, no constraints – they will come from the clauses now.

x1

x2

vend

xn−1

xn

vstart

38 / 177

Clause Constraints

Each clause Cj corresponds to a new vertex u_j.

If Cj contains a non-negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk+1 in the xi chain

x

u

Clause Constraints

Each clause Cj corresponds to a new vertex u_j.

If Cj contains a non-negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk+1 in the xi chain

x

u

40 / 177

Clause Constraints

Each clause Cj corresponds to a new vertex u_j.

If Cj contains a non-negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk+1 in the xi chain

x

u

Clause Constraints

Each clause Cj corresponds to a new vertex u_j.

If Cj contains a non-negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk+1 in the xi chain

x

u

42 / 177

Clause Constraints

Each clause Cj corresponds to a new vertex u_j.

If Cj contains a non-negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk+1 in the xi chain

x

u

Clause Constraints

If Cj contains a negated literal, reverse the edge directions

If Cj contains a negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk−1 in the xi chain

x

u

44 / 177

Clause Constraints

If Cj contains a negated literal, reverse the edge directions If Cj contains a negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk−1 in the xi chain

x

u

Clause Constraints

If Cj contains a negated literal, reverse the edge directions If Cj contains a negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk−1in the xi chain

x

u

46 / 177

Clause Constraints

If Cj contains a negated literal, reverse the edge directions If Cj contains a negated literal x_i, add edges to u_j:

I Add an incoming edge from a vertex, say vk, in the xi chain

I Add an outgoing edge to vk−1in the xi chain

x

u

An Example

Construction of Hamiltonian path for

(a∨ b) ∧ (a ∨ b) Here:

C1= (a∨ b) C2= (a∨ b)

48 / 177

The Graph Construction

a

b

v_start

vend

a ∨ b

a ∨ b

Claim

Hamiltonian path exists ONLYif you go from left to right ina and chose any one of the two directions for b.

The Graph Construction

a

b

v_start

vend

a ∨ b

a ∨ b

Claim

Hamiltonian path exists ONLYif you go from left to right ina and chose any one of the two directions for b.

50 / 177

Path Corresponding to Assignment 1

a = 1; b = 1

a

b

vstart

a ∨ b

a ∨ b

Path Corresponding to Assignment 2

a = 1; b = 0

a

b

vstart

vend

a ∨ b

a ∨ b

52 / 177

Path Corresponding to Assignment 3

a = 0; b = 1

a

b

vstart

vend

a ∨ b

a ∨ b

Path Corresponding to Assignment 4

a = 0; b = 0

a

b

vstart

vend

a ∨ b

a ∨ b

Error in finding HAMILTONIAN

No HAMILTONIAN PATH as (a∨ b) is not accessible

54 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction: Any Hamiltonian path has to start at vstart

Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc. For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at vstart

Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc. For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

56 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start

Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc. For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc. For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

58 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it. Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path. Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

60 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path.

Each path corresponds to a unique variable assignment. If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path.

Each path corresponds to a unique variable assignment.

If x_i ∈ Cj and x_i = 1, can visit uj along the way. If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

62 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path.

Each path corresponds to a unique variable assignment.

If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path.

Each path corresponds to a unique variable assignment.

If x_i ∈ Cj and x_i = 1, can visit uj along the way.

If x_i ∈ Cj and x_i = 0, can visit uj along the way.

The above two only ways to visit u_j without getting stuck.

64 / 177

Construction Claim

Claim

The constructed graph G has a Hamiltonian path iff φ satisfiable.

Things to note about the final construction:

Any Hamiltonian path has to start at v_start Any Hamiltonian path has to end at v_end

Any Hamiltonian path first traverses chain x₁, then x₂ etc.

For each chain, only two ways of traversing it.

Each assignment of variables corresponds to a path.

Each path corresponds to a unique variable assignment.

If x_i ∈ Cj and x_i = 1, can visit uj along the way.

SET-COVER

Claim

SET-COVER : A collectionC = {S1, . . . , Sm} of subsets of a base set X ,

|X | = n, and parameter k, find a set cover C⁰⊆ C of size k The set cover problem (SET-COVER ) is NP complete.

C⁰={Si1, . . . , Sik} is a set-cover iff S_jS_ij = X .

Note that SET-COVER is in NP How to prove NP hardness? Reduce from VERTEX-COVER

66 / 177

SET-COVER

Claim

SET-COVER : A collectionC = {S1, . . . , Sm} of subsets of a base set X ,

|X | = n, and parameter k, find a set cover C⁰⊆ C of size k The set cover problem (SET-COVER ) is NP complete.

C⁰={Si1, . . . , Sik} is a set-cover iff S_jS_ij = X .

Note that SET-COVER is in NP How to prove NP hardness? Reduce from VERTEX-COVER

SET-COVER

Claim

SET-COVER : A collectionC = {S1, . . . , Sm} of subsets of a base set X ,

|X | = n, and parameter k, find a set cover C⁰⊆ C of size k The set cover problem (SET-COVER ) is NP complete.

C⁰={Si1, . . . , Sik} is a set-cover iff S_jS_ij = X . Note that SET-COVER is in NP

How to prove NP hardness? Reduce from VERTEX-COVER

68 / 177

SET-COVER

Claim

SET-COVER : A collectionC = {S1, . . . , Sm} of subsets of a base set X ,

|X | = n, and parameter k, find a set cover C⁰⊆ C of size k The set cover problem (SET-COVER ) is NP complete.

C⁰={Si1, . . . , Sik} is a set-cover iff S_jS_ij = X .

Note that SET-COVER is in NP How to prove NP hardness?

Reduce from VERTEX-COVER

SET-COVER

Claim

SET-COVER : A collectionC = {S1, . . . , Sm} of subsets of a base set X ,

|X | = n, and parameter k, find a set cover C⁰⊆ C of size k The set cover problem (SET-COVER ) is NP complete.

C⁰={Si1, . . . , Sik} is a set-cover iff S_jS_ij = X .

Note that SET-COVER is in NP How to prove NP hardness?

Reduce from VERTEX-COVER

70 / 177

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover. The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover. The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

72 / 177

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

74 / 177

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci ={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover. Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

76 / 177

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci ={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover.

Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci ={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover.

Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

78 / 177

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci ={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover.

Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

Reduction from VERTEX-COVER

Given a graph G = (V, E), the idea is that:

I Each vertex vi maps to a setCi

I {vi₁, . . . , vi_k} is a vertex-cover iff {Ci₁, . . . , Ci_k} is a set-cover.

The exact construction is as follows:

I Each edge ej ∈ E maps to an element aj ∈ X .

I Each vertex vi∈ V maps to set Ci ={aj s.t. ej incident to vi}

Claim

V⁰ ={vi1, . . . , vik} is a vertex-cover iff {Cii, . . . , Cik} is a set cover.

Proof.

If e_j incident to v_i, then set C_i contains a_j

Picking v_i covers all edges incident to v_i ⇐⇒ picking Ci covers all corresponding elements a_j

V⁰ covers all edges ⇐⇒ C⁰ cover all elements

80 / 177

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING

Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k: Integer program variables: x_j = 1 iff Sj picked in set-cover

At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program

GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k: Integer program variables: x_j = 1 iff Sj picked in set-cover

At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

82 / 177

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover

At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

84 / 177

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets:

X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

86 / 177

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k All elements covered:

X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i

Variable 0 or 1: x_i ∈ {0, 1}

88 / 177

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i

x_i ∈ {0, 1}

Another Hardness Proof for INTEGER-PROGRAMMING

Another reduction for INTEGER-PROGRAMMING SET-COVER can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the set-cover problem as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff Sj picked in set-cover At most k sets: X

j

x_j ≤ k

All elements covered: X

j |ai∈Sj

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

90 / 177

Yet Another Hardness Proof for INTEGER-PROGRAMMING

Yet another reduction for INTEGER-PROGRAMMING HITTING-SET can be reduced to INTEGER-PROGRAMMING

Proof.

Formulate the hitting-set as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k: Integer program variables: x_j = 1 iff xj picked in hitting-set

At most k elements: X

j

x_j ≤ k

All sets covered: X

j |aj∈Si

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Yet Another Hardness Proof for INTEGER-PROGRAMMING

Yet another reduction for INTEGER-PROGRAMMING HITTING-SET can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the hitting-set as an integer program

GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k: Integer program variables: x_j = 1 iff xj picked in hitting-set

At most k elements: X

j

x_j ≤ k

All sets covered: X

j |aj∈Si

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

92 / 177

Yet Another Hardness Proof for INTEGER-PROGRAMMING

Yet another reduction for INTEGER-PROGRAMMING HITTING-SET can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the hitting-set as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff xj picked in hitting-set At most k elements: X

j

x_j ≤ k

All sets covered: X

j |aj∈Si

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

Yet Another Hardness Proof for INTEGER-PROGRAMMING

Yet another reduction for INTEGER-PROGRAMMING HITTING-SET can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the hitting-set as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff xj picked in hitting-set

At most k elements: X

j

x_j ≤ k

All sets covered: X

j |aj∈Si

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}

94 / 177

Yet Another Hardness Proof for INTEGER-PROGRAMMING

Yet another reduction for INTEGER-PROGRAMMING HITTING-SET can be reduced to INTEGER-PROGRAMMING Proof.

Formulate the hitting-set as an integer program GivenC = {S1, . . . , Sm} over X = {a1, . . . , an} and k:

Integer program variables: x_j = 1 iff xj picked in hitting-set At most k elements:

X

j

x_j ≤ k

All sets covered: X

j |aj∈Si

x_j ≥ 1 ∀i Variable 0 or 1: x_i ∈ {0, 1}