CS21 Decidability and Tractability
Lecture 20
February 21, 2024
Copyright By PowCoder代写 加微信 powcoder
• NP-complete problems: independent set, vertex cover, clique…
• NP-complete problems: Hamilton path and cycle,Traveling Salesperson Problem
• NP-complete problems: Subset Sum
• NP-complete problems: NAE-3-SAT, max cut
February 21, 2024 CS21 Lecture 20 2
Search vs. Decision
• Definition: given a graph G = (V, E), an independent set in G is a subset V’⊆ V suchthatforallu,w∈V’ (u,w)∉E
• A problem:
given G, find the largest independent set
• This is called a search problem
– searching for optimal object of some type – comes up frequently
February 21, 2024 CS21 Lecture 20 3
Search vs. Decision
• We want to talk about languages (or
decision problems)
• Most search problems have a natural, related decision problem by adding a bound “k”; for example:
– search problem: given G, find the largest independent set
– decision problem: given (G, k), is there an independent set of size at least k
February 21, 2024 CS21 Lecture 20 4
Ind. Set is NP-complete
Theorem: the following language is NP- complete:
IS = {(G, k) : G has an IS of size ≥ k}.
– Part 1: IS ∈ NP. Proof?
– Part 2: IS is NP-hard. • reduce from 3-SAT
February 21, 2024 CS21 Lecture 20 5
Ind. Set is NP-complete • We are reducing from the language:
3SAT = { φ : φ is a 3-CNF formula that has a satisfying assignment }
to the language:
IS = {(G, k) : G has an IS of size ≥ k}.
February 21, 2024 CS21 Lecture 20 6
Ind. Set is NP-complete
The reduction f: given
φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ w ∨ z) ∧… ∧ (…)
we produce graph Gφ:
• onetriangleforeachofmclauses
• edgebetweeneverypairofcontradictoryliterals
February 21, 2024 CS21 Lecture 20 7
Ind. Set is NP-complete φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ w ∨ z) ∧… ∧ (…)
(G, # clauses)
x ¬x y ¬zw z
• Is f poly-time computable?
• YES maps to YES?
– 1 true literal per clause in satisfying assign. A – choose corresponding vertices (1 per triangle) – IS, since no contradictory literals in A
February 21, 2024 CS21 Lecture 20 8
Ind. Set is NP-complete φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ w ∨ z) ∧… ∧ (…)
(G, # clauses)
x¬x y ¬zw z
– IS can have at most 1 vertex per triangle
– IS of size ≥ # clauses must have exactly 1 per
– since IS, no contradictory vertices
– can produce satisfying assignment by setting these literals to true
February 21, 2024 CS21 Lecture 20 9
• NO maps to NO?
Vertex cover
• Definition: given a graph G = (V, E), a vertex cover in G is a subset V’ ⊆ V such that for all (u,w) ∈ E, u ∈ V’ or w ∈ V’
• A search problem:
given G, find the smallest vertex cover
• corresponding language (decision problem): VC = {(G, k) : G has a VC of size ≤ k}.
February 21, 2024 CS21 Lecture 20 10
Vertex Cover is NP-complete
Theorem: the following language is NP- complete:
VC = {(G, k) : G has a VC of size ≤ k}.
– Part 1: VC ∈ NP. Proof?
– Part 2: VC is NP-hard. • reduce from?
February 21, 2024 CS21 Lecture 20 11
Vertex Cover is NP-complete • We are reducing from the language:
IS = {(G, k) : G has an IS of size ≥ k} to the language:
VC = {(G, k) : G has a VC of size ≤ k}.
February 21, 2024 CS21 Lecture 20 12
Vertex Cover is NP-complete • How are IS, VC related?
• GivenagraphG=(V,E)withnnodes
– if V’ ⊆ V is an independent set of size k – then V-V’ is a vertex cover of size n – k
– suppose not. Then there is some edge with neither endpoint in V-V’. But then both endpoints are in V’. contradiction.
February 21, 2024 CS21 Lecture 20 13
Vertex Cover is NP-complete • How are IS, VC related?
• GivenagraphG=(V,E)withnnodes
– if V’ ⊆ V is a vertex cover of size k
– then V-V’ is an independent set of size n – k
– suppose not. Then there is some edge with both endpoints in V-V’. But then neither endpoint is in V’. contradiction.
February 21, 2024 CS21 Lecture 20 14
Vertex Cover is NP-complete
The reduction:
– given an instance of IS: (G, k) f produces the pair (G, n-k)
• f poly-time computable? • YES maps to YES?
– IS of size ≥ k in G ⇒ VC of size ≤ n-k in G • NO maps to NO?
– VC of size ≤ n-k in G ⇒ IS of size ≥ k in G February 21, 2024 CS21 Lecture 20 15
• Definition: given a graph G = (V, E), a clique in G is a subset V’⊆ V such that for all u,v ∈ V’, (u, v) ∈ E
• A search problem:
given G, find the largest clique
• corresponding language (decision problem): CLIQUE = {(G, k) : G has a clique of size ≥ k}.
February 21, 2024 CS21 Lecture 20 16
Clique is NP-complete
Theorem: the following language is NP- complete:
CLIQUE = {(G, k) : G has a clique of size ≥ k}
– Part 1: CLIQUE ∈ NP. Proof?
– Part 2: CLIQUE is NP-hard. • reduce from?
February 21, 2024 CS21 Lecture 20 17
Clique is NP-complete • We are reducing from the language:
IS = {(G, k) : G has an IS of size ≥ k} to the language:
CLIQUE = {(G, k) : G has a CLIQUE of size ≥ k}. February 21, 2024 CS21 Lecture 20 18
Clique is NP-complete • HowareIS,CLIQUErelated?
• GivenagraphG=(V,E),defineitscomplement G’ = (V, E’ = {(u,v) : (u,v) ∉ E})
– ifV’⊆VisanindependentsetinGofsizek – thenV’isacliqueinG’ofsizek
– Every pair of vertices u,v ∈ V’ has no edge between them in G. Therefore they have an edge between them in G’.
February 21, 2024 CS21 Lecture 20 19
Clique is NP-complete • HowareIS,CLIQUErelated?
• GivenagraphG=(V,E),defineitscomplement G’ = (V, E’ = {(u,v) : (u,v) ∉ E})
– ifV’⊆VisacliqueinG’ofsizek
– then V’ is an independent set in G of size k
– Every pair of vertices u,v ∈ V’ has an edge between them in G’. Therefore they have no edge between them in G.
February 21, 2024 CS21 Lecture 20 20
Clique is NP-complete
The reduction:
– given an instance of IS: (G, k) f produces the pair (G’, k)
• f poly-time computable? • YES maps to YES?
– IS of size ≥ k in G ⇒ CLIQUE of size ≥ k in G’ • NO maps to NO?
– CLIQUE of size ≥ k in G’ ⇒ IS of size ≥ k in G February 21, 2024 CS21 Lecture 20 21
Hamilton Path
• Definition: given a directed graph G = (V, E), a Hamilton path in G is a directed path that touches every node exactly once.
• A language (decision problem):
HAMPATH = {(G, s, t) : G has a Hamilton path
from s to t}
February 21, 2024 CS21 Lecture 20 22
HAMPATH is NP-complete
Theorem: the following language is NP- complete:
HAMPATH = {(G, s, t) : G has a Hamilton path from s to t}
– Part 1: HAMPATH ∈ NP. Proof?
– Part 2: HAMPATH is NP-hard. • reduce from?
February 21, 2024 CS21 Lecture 20 23
HAMPATH is NP-complete • We are reducing from the language:
3SAT = { φ : φ is a 3-CNF formula that has a satisfying assignment }
to the language:
HAMPATH = {(G, s, t) : G has a Hamilton path from s to t}
February 21, 2024 CS21 Lecture 20 24
HAMPATH is NP-complete
• We want to construct a graph from φ with the following properties:
– a satisfying assignment to φ translates into a Hamilton Path from s to t
– a Hamilton Path from s to t can be translated into a satisfying assignment for φ
• We will build the graph up from pieces called gadgets that “simulate” the clauses and variables of φ.
February 21, 2024 CS21 Lecture 20 25
HAMPATH is NP-complete • The variable gadget (one for each xi):
February 21, 2024
CS21 Lecture 20
HAMPATH is NP-complete
• path from s to t translates into a truth assignment to x1…xm
• why must the path be of this form?
February 21, 2024
… “xm” CS21 Lecture 20
HAMPATH is NP-complete φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…)
• How to ensure that all k clauses are satisfied?
• need to add nodes
– can be visited in path if the clause is satisfied
– if visited in path, implies clause is satisfied by the assignment given by path through variable gadgets
February 21, 2024 CS21 Lecture 20 28
HAMPATH is NP-complete
φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…)
• Clause gadget allows “detour” from “assignment path” for each true literal in clause “x1” …
February 21, 2024
“x2” … “x3” …
CS21 Lecture 20
HAMPATH is NP-complete
• One clause gadget for each of k clauses:
for clause 1
February 21, 2024
for clause 2
CS21 Lecture 20
HAMPATH is NP-complete
φ=(x1 ∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)…
“C1” • f(φ) is this graph (edges
“C2” to/from clause nodes not
• f poly-time computable?
• # nodes = O(km)
February 21, 2024
CS21 Lecture 20
HAMPATH is NP-complete
φ=(x1 ∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)…
• YES maps to YES?
• first form
path from : satisfying
“Ck” assign.
• pick true literal in each clause and add detour
February 21, 2024
CS21 Lecture 20
HAMPATH is NP-complete
φ=(x1 ∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)…
• NO maps to NO?
• try to translate path into satisfying assignment
• if path has “intended” form, OK.
February 21, 2024
CS21 Lecture 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com