0017 Computational Complexity problem sheet 6.
1. Give a precise definition of the Travelling Salesman Problem (TSP) and the Travelling Salesman Decision Problem (TSDP).
Solution: A TSP instance is a tuple (G,f), where G is a complete graph and f is a function from edges to non-negative integers. A solution to such an instance is the length of the shortest circtuit in G.
A TSDP instance is a tuple (G, f, d) where G is a complete graph, f is a non-negative weight function and d is a non-negative integer. This is a yes-instance if there is a circuit of G of total length (weight) not more than d; otherwise, it is a no-instance.
Copyright By PowCoder代写 加微信 powcoder
2. A student has won a voucher that allows her to visit each European capital city exactly once and return to her starting city. She must take direct connections from one city to the next but she can visit the capital cities in any order she likes. She wishes to travel the maximum distance possible. The student holiday decision problem (SHDP) can be formalised as follows. An instance is a tuple (G, f, d), which consists of a complete graph G, a weight function f mapping edges of G to non-negative integers, and a non-negative integer d. A circuit of G is any enumeration (g0, g1, . . . , gk−1) of the nodes of G and the weight of this circuit is f(g0, g1) + f(g1, g2) + · · · + f(gk−2, gk−1) + f(gk−1, g0). The instance (G,f,d) is a yes-instance of SHDP if there is a circuit whose weight is at least d; it is a no-instance otherwise.
Say which of the following three instances are yes-instances of SHDP and which are no-instances.
(a) d = 0 (b) d = 14 (c) d = 33 Solution: Let us consider the graphs one-by-one.
(a) Since d = 0, any cycle will do; since the graph is complete (by definition of the SHDP), it follows that this is a yes-instance.
(b) We can start at the lower left node, take the diagonal to the upper right node, move to the upper left node, take the diagonal down to the lower right node and then move back to the lower left node. The total weight of this path is 7+4+3+0 = 14, which is exactly enough for this to be a yes-instance.
(c) This is a no-instance; the proof to see this is a little bit involved. Suppose towards a contradiction that this graph is a yes-instance, and furthermore that the circuit of weight at least 33 does not contain the edge labelled by 9. This means that of the remaining edges, we have to choose five edges with a total weight of 33. How- ever, if we choose any five of the remaining edges, the maximum total weight (even disregarding the constraint that they have to formacircuit)is8+7+6+5+5=31. Thus,ifthereexistsa circuit of weight 33, it must contain the edge labelled by 9.
Now suppose towards a contradiction that this graph is a yes- instance, and furthermore that the circuit of weight at least 33 does not contain the edge labelled by 8. From the above, we already know that the edge labelled by 9 is in the circuit. This means that there are four remaining edges of a total weight at least 33 − 9 = 24. However, if we choose any four of the remaining edges, the maximum weight (again disregarding the constraint thattheyhavetoformacircuit)is7+6+5+5=23. Thus,if there exists a circuit of weight at least 33, it must also contain the edge labelled by 8.
By a similar argument, we can show that if there exists a circuit of weight at least 33, then this circuit must also contain the edge labelled by 7. Now, suppose this circuit, which moves from the lower left node to the lower right node, then up to the upper right node and then the upper left node, can be completed into a circuit of length at least 33. The only remaining node that we need to visit is the central node, and the weight that we still need is 33−7−9−8 = 9. However, the only edges that we can add to complete the circuit have a total weight of 2 + 4 = 6. Hence, this circuit of total length at least 33 cannot exist.
3. Suppose that P is a program that solves SHDP. Using pseudo-code, de- fine an algorithm that uses P as a subroutine and returns the maximum possible circuit length of any circuit of any instance (G,f).
Solution: First, note that the total weight of a circuit in G is bound from above by the maximum weight of an edge multiplied by the number of edges in the circuit. Since the number of edges in the circuit is the same as the number of nodes, we can simply multiply the maximum weight by the number of nodes to obtain this upper bound. The algorithm to find the maximum possible circuit length then simply counts down using a counter i from this upper bound and calls P to find out if there is a circuit of weight at least i. The first time such a circuit is found, it must be the circuit of maximum weight, since we are counting down.
The pseudocode for this algorithm is as follows:
Function MaxCircuit(G: graph, f: weight function): m ← max edge weight in G
m ← number of nodes in G
for i = m × n down to zero do
if P(G,f,i) = yes then return i
4. Define a polynomial time reduction of TSDP to SHDP and show that your reduction is correct.
Solution: Let (G, f, d) be an instance of TSDP. Let n be number of nodes of G and let m be the maximum edge weight under f — note that it takes linear time to calculate n,d. First, define f′ by f′(e) = m−f(e) for all edges e, and observe that f′ returns a non-negative integer. Furthermore, note that f(e) = m − f′(e) by construction.
We create an instance of SHDP as follows. The reduction maps (G, f, d) to (G, f′, n × m − d). Clearly, it requires only polynomial time to compute this. We argue correctness as follows.
(⇒) Suppose (G,f,d) is a yes-instance of TSDP; let γ be a circuit whose total weight under f is w ≤ d. Then the weight of γ under f′ isn×m−w≥n×m−d. Therefore,(G,f′,n×m−d)isa yes-instance of SHDP.
(⇐) Conversely, suppose (G,f′,n×m−d) is a yes-instance of SHDP; let γ be a circuit whose weight under f′ is w ≥ n × m − d. Then γ has total weight n×m−w ≤ n×m−(n×m−d) = d, so
(G, f, d) is a yes-instance of TSDP.
5. Suppose the run-time of the program P (above) is O(n3), where n is the size of an instance of SHDP suitably coded. What does this tell you, if anything, about the complexity class NP? Explain your answer and state which previous parts of this question you need to use. You may assume that TSDP is NP-complete.
Solution: If this is true, then NP = P. To see this, suppose that A ∈ NP. Since TSDP is NP-complete, we have A ≤p TSDP. We showed in previous part of this question that TSDP ≤p SHDP. By transitivity of ≤p it follows that A ≤p SHDP. Now A can be solved in polynomial time by first reducing to SHDP and then running P. This takes polynomial time, and therefore A ∈ P. Hence, NP ⊆ P.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com