程序代写代做代考 Microsoft PowerPoint – lecture15 [Compatibility Mode]

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