CS21 Decidability and Tractability
Lecture 21 February 23, 2024
• NP-complete problems: independent set, vertex cover, clique…
• NP-complete problems: Hamilton path and cycle,Traveling Salesperson Problem
Copyright By PowCoder代写 加微信 powcoder
• NP-complete problems: Subset Sum
• NP-complete problems: NAE-3-SAT, max cut
February 23, 2024 CS21 Lecture 21 2
“x1” “x2 ”
February 23, 2024
HAMPATH is NP-complete
φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)…
CS21 Lecture 21
“C1” • NO maps to NO?
• try to translate path into satisfying assignment
• if path has “intended” form, OK.
HAMPATH is NP-complete
• What can go wrong?
– path has “intended form” unless return from
clause gadget to different variable gadget
that this “xj” cannot happen: “xh ”
February 23, 2024
CS21 Lecture 21
… … …
HAMPATH is NP-complete
Case 1 (positive occurrence of v in clause):
• path must visit y
• must enter from x, z, or c
• must exit to z (x is taken)
• x, c are taken. can’t happen
February 23, 2024
CS21 Lecture 21
February 23, 2024
CS21 Lecture 21
HAMPATH is NP-complete
Case 2 (negative occurrence of v in clause):
• path must visit y
• must enter from x or z
• must exit to z (x is taken)
• x is taken. can’t happen
Undirected Hamilton Path
• HAMPATH refers to a directed graph. • Is it easier on an undirected graph?
• A language (decision problem):
UHAMPATH = {(G, s, t) : undirected G has a Hamilton path from s to t}
February 23, 2024 CS21 Lecture 21 7
UHAMPATH is NP-complete
Theorem: the following language is NP- complete:
UHAMPATH = {(G, s, t) : undirected graph G has a Hamilton path from s to t}
– Part 1: UHAMPATH ∈ NP. Proof?
– Part 2: UHAMPATH is NP-hard. • reduce from?
February 23, 2024 CS21 Lecture 21 8
UHAMPATH is NP-complete • We are reducing from the language:
HAMPATH = {(G, s, t) : directed graph G has a Hamilton path from s to t}
to the language:
UHAMPATH = {(G, s, t) : undirected graph G has a Hamilton path from s to t}
February 23, 2024 CS21 Lecture 21 9
UHAMPATH is NP-complete
• The reduction:
February 23, 2024
uin umid uout
vin vmid vout
• replace each node with three (except s, t)
• (uin, umid) • (umid, uout)
• (uout, vin) iff G has (u,v) 10
CS21 Lecture 21
UHAMPATH is NP-complete • Does the reduction run in poly-time?
• YES maps to YES?
– Hamilton path in G: s, u1, u2, u3, …, uk, t – Hamilton path in G’:
sout, (u1)in, (u1)mid, (u1)out, (u2)in, (u2)mid, (u2)out, … (uk)in, (uk)mid, (uk)out, tin
February 23, 2024 CS21 Lecture 21 11
UHAMPATH is NP-complete
• NO maps to NO?
– Hamilton path in G’:
sout, v1, v2, v3, v4, v5, v6, …, vk-2, vk-1, vk, tin – v1 = (ui1)in for some i1 (only edges to ins)
– v2 = (ui1)mid for some i1 (only way to enter mid) – v3 = (ui1)out for some i1 (only way to exit mid) – v4 = (ui2)in for some i2 (only edges to ins)
– Hamilton path in G: s, ui1, ui2, ui3, …, uik, t
February 23, 2024 CS21 Lecture 21 12
Undirected Hamilton Cycle
• Definition: given a undirected graph G = (V, E), a Hamilton cycle in G is a cycle in G that touches every node exactly once.
• Is finding one easier than finding a Hamilton path?
• A language (decision problem): UHAMCYCLE = {G : G has a Hamilton cycle}
February 23, 2024 CS21 Lecture 21 13
UHAMCYCLE is NP-complete
Theorem: the following language is NP- complete:
UHAMCYCLE = {G: G has a Hamilton cycle} • Proof:
– Part 1: UHAMCYCLE ∈ NP. Proof? – Part 2: UHAMCYCLE is NP-hard.
• reduce from?
February 23, 2024 CS21 Lecture 21 14
UHAMCYCLE is NP-complete • The reduction (from UHAMPATH):
• H. path from s to t implies H. cycle in G’
• H. cycle in G’ must visit u via red edges
• removing red edges gives H. path from s to t in G
February 23, 2024 CS21 Lecture 21 15
Traveling Salesperson Problem
• Definition: given n cities v1, v2, …, vn and inter-city distances di,j a TSP tour in G is a permutation 𝜋 of {1…n}. The tour’s length is Σi = 1…n d𝜋(i),𝜋(i+1) (where n+1 means 1).
• A search problem:
given the {di,j}, find the shortest TSP tour
• corresponding language (decision problem): TSP={({di,j :1≤i