Discussion 11
1. In the Min-Cost Fast Path problem, we are given a directed graph G=(V,E) along with positive integer times te and positive costs ce on each edge. The goal is to determine if there is a path P from s to t such that the total time on the path is at most T and the total cost is at most C (both T and C are parameters to the problem). Prove that this problem is NP-complete.
Solution:
1-
2- 3-
Prove that Min-Cost Fast Path is in NP
Certificate: an s-t path with total cost ≤C and total time ≤T Certifier: Can easily check in polynomial time that
a- Set of edges given are in fact a path from s-t
b- Total time is ≤T and total cost is ≤C
a and b can be easily done in polynomial time. Min-Cost Fast Path ε NP Choose Subset Sum for our reduction
Will show that Subset Sum ≤p Min-Cost Fast Path
Background: Decision version of the Subset Sum problem asks whether given n items where item i has weight wi, if there is a subset of them whose total weight is less than W and greater than M.
Plan: We build a graph G such that it has an s-t path with total cost ≤W and total time ≤Σwi – M iff there is a subset of items whose total weight is between M and W.
We use gadgets to represent each item. Each gadget will offer two paths through the gadget. If the s-t path in G goes through the A node of the gadget we can interpret that as item being selected as part of the set. If the s-t path goes through the B node of the gadget we interpret that as the item not being selected as part of the set. We string up the gadgets and set time te and costs ce to edges as follows:
S
c=w1 t=0
c=0 t=w1
A1
B1
c,t=0
c,t=0
c=w 2
t=0
c=0
t=w 2
A2
B2
c,t=0
c,t=0
c=w n
t=0
c=0 t=wn
An
Bn
c,t=0
T c,t=0
Proof:
A- IfwearegivenasetofitemswithtotalweightbetweenMandW,wecanfindapathfromS
to T with total cost of at most W and total time of at most Σwi – M by choosing the path through each gadget based on whether the item is part of the set (Go through the A node) or not (go through the B node). If we go through the A node for object i, the object contributes wi to the cost of the path and if we go through the B node, the object contributes wi to the total time for the path. So the total cost for the path will be the total weight of the objects selected which we know if ≤ W and the total time of the path is total weight of the objects that are not selected which we know is Σwi – M (because we know the total weight of the objects selected is ≥ M)
B- IfwearegivenapathfromStoTwhichhasatotalcostofatmostWandatotaltimeofat most Σwi – M, we can find a set of objects with total weight between M and W. The S-T path can easily select the objects that belong to the set. If the path goes through the A node for an object, we place that object in the set, otherwise not. Since the total cost of the path is at most W then the total weight of the objects selected will be at most W and since the total time for the path is at most Σwi – M, the total weight of the objects not selected will be Σwi – M, which means that the total weight of objects selected will be at least M.
2. We saw in lecture that finding a Hamiltonian Cycle in a graph is NP-complete. Show that finding a Hamiltonian Path — a path that visits each vertex exactly once, and isn’t required to return to its starting point — is also NP-complete.
Solution:
4- Prove that Hamiltonian Path is in NP
Certificate: an ordering of all nodes in G that forms a Hamiltonian Path Certifier: Can easily check in polynomial time that
a- There is an edge between each pair of adjacent vertices in the given order
b- All nodes in G are visited by the path
a and b can be easily done in polynomial time. Hamiltonian Path ε NP
5- Choose Hamiltonian Cycle for our reduction
6- Will show that Hamiltonian Cycle ≤p Hamiltonian Path
Plan: Given graph G—an instance of the Hamiltonian Cycle problem, we will construct G’ such that G’ has a Hamiltonian Path iff G has a Hamiltonian Cycle.
Construction of G’. We will split one of the nodes in G, say node A. Nodes A and A’ will have the same connections as the original node A in G. We will then add two node nodes S and T and connect one with A and the other with A’.
Now G’ has a Hamiltonian Path from S to T iff there is a Hamiltonian Cycle in G.
T
S
A
A’
A
G
G’
Proof:
A- IfwearegivenaHamiltonianPathinG’,sinceSandThaveadegreeof1,andcanonlybe
the beginning or the end of the path, the path must go from S to T. Ignoring the two new edges SA and TA’, this path will give us a Hamiltonian Cycle in G since A and A’ are the same node in G, i.e. the path will start and end at the same node (A).
B- IfwearegivenaHamiltonianCycleinG,wecancreateaHamiltonianPathinG’bysplitting the Cycle at node A and creating a path from A’ to A. We can then form a Hamiltonian Path in G’ by starting at S going to A, following the Hamiltonian Cycle to A’ and end the Path at T.
3. Some NP-complete problems are polynomial-time solvable on special types of graphs, such as bipartite graphs. Others are still NP-complete.
Show that the problem of finding a Hamiltonian Cycle in a bipartite graph is still NP-complete.
Solution:
7- Prove that Hamiltonian Cycle in a bipartite graph is in NP
Certificate: an ordering of all nodes in G that forms a Hamiltonian Cycle Certifier: Can easily check in polynomial time that
a- There is an edge between each pair of adjacent vertices in the given order
b- All nodes in G are visited by the path
c- There is an edge between the last node in the order and the first node
a, b and c can be easily done in polynomial time. Hamiltonian Cycle in a bipartite graph ε NP
8- Choose Hamiltonian Cycle for our reduction
9- Will show that Hamiltonian Cycle ≤p Hamiltonian Cycle in a bipartite graph
Plan: Given graph G—an instance of the Hamiltonian Cycle problem, we will construct G’ such that G’ is bipartite and has a Hamiltonian Cycle iff G has a Hamiltonian Cycle.
Construction of G’: For each node A in G we will use a gadget with four nodes as shown below. If A and B are connected in G, we connect nodes A1 and B4 and nodes B1 and A4 in G’.
A4
A3 A2
A1
Gadget in G’ representing the node A in G
C4
A4
B4
C
A
C1
B1
A1
G’
G
B
G’ is bipartite since we place all nodes V1 and V3 into the set X and nodes V2 and V4 into the set Y, all edges in G’ go between sets X and Y. And G’ has a Hamiltonian Cycle iff G has a Hamiltonian Cycle.
Proof:
A- If we are given a Hamiltonian Cycle in G’ it must be of the form V1 V2 V3 V4 U1 U2 U3 U4 ….. V1 since there is no other way for the Hamiltonian Cycle to go through the nodes of each gadget. We can then use the same sequence of nodes V, U, …., V to form a Hamiltonian Cycle in G, since if there is a connection between V4 and U1 in G’, there must be an edge between V and U in G.
B- If we are given a Hamiltonian Cycle in G that goes through nodes V, U, …., V we can form a Hamiltonian Cycle in G’ by going through the gadgets corresponding to nodes V, U, …., V i.e. nodes V1 V2 V3 V4 U1 U2 U3 U4 ….. V1 since if there is a connection between nodes V and U, there must be a connection between nodes V4 and U1 in G’.