Microsoft PowerPoint – lecture15 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 15, 3/6/18
Set Cover Problem
• Input: A family F of (finite) sets S1,…,Sm with union U (the
universe of elements)
Want to find a subfamily F’ of F with the fewest possible
sets that covers U, i.e. whose union is U
• Decision version: Input: set family F, number k
• Question: cover of size ≤k?
• Node Cover is a special case:
• U = set E of edges of the given graph G=(V,E)
• F: one set Si for every node vi V that contains all the
edges incident to vi
(Directed) Hamiltonicity
• Input: (Directed) graph H
• Question: Hamiltonian cycle (cycle that visits every
vertex exactly once)?
• In NP: certificate = Hamiltonian cycle
• NP-hard: Reduction from Node Cover
• Given (graph G, k)=instance of Node cover, construct
another graph H such that G has a node cover of size k
iff H has a Hamiltonian cycle
Node Cover ≤log Directed Hamiltonicity
• Nodes of H: k “selector” nodes s1,…sk and
4 nodes for every edge (u,v) connected as in the following
“gadget”:
[u,v,1]
[u,v,2]
[v,u,1]
[v,u,2]
Outside edges only into [.,.,1], and out of [.,.,2]
Three ways to cover the nodes of the gadget:
1. enter at [u,v,1], visit all nodes and leave at [u,v,2]
2. enter at [v,u,1], visit all nodes and leave at [v,u,2]
3. [u,v,1] to [u,v,2] …. later on [v,u,1] to [v,u,2]
Node Cover ≤log Directed Hamiltonicity ctd.
• Ignore isolated nodes of G (if it has any)
• For each node u of G, all [u,v,1],[u,v,2] nodes are connected in a path
(in arbitrary order of u’s edges), first node of path has edge from all
selector nodes, last node has edge to all selector nodes
s1 … sk
gadget for
edge (u,v)
path for u path for v
G has node cover
with k nodes
H is Hamiltonian
Directed Hamiltonicity ≤log Undirected
x
y
z
v
w
u
u1 u2 u3
x3
y3
z3
v1
w1
Hamiltonicity variants
• Hamiltonian path: A path that visits every node
exactly once
• NP-complete to determine if a given undirected
or directed graph has
• a Hamiltonian path (with any endpoints)
• a Hamiltonian path with specified endpoints s,t
(HW Exercise)
Traveling Salesman Problem
• Input: Complete undirected graph G with weights d(i,j)>0
on its edges (“n cities and their pairwise distances”)
• Output: Shortest (minimum total distance) “tour”
(Hamilton cycle) that visits every city exactly once.
• Decision version: Given (G,d) and bound b, is there a
“tour” with total distance ≤b ?
• In NP: certificate= tour
• NP-hard: Reduction from Undirected Hamiltonicity
• Given graph H=(N,E), let G have same nodes and define
d(i,j)=1 if (i,j)E, else d(i,j)=2. Then H is Hamiltonian iff G
has a tour with total distance ≤n