COMP0017 — Exercises 7 Hamiltonian Path Problem.
November 27, 2020
Questions 1, 2, 3 and 6 are fairly straightforward. Questions 4 and 5 are harder.
1. Define carefully what we mean when we say that a decision problem is NP-hard.
Copyright By PowCoder代写 加微信 powcoder
Ans: A is NPH if for all B in NP we have B ≤p A.
2. Define the Hamiltonian Circuit Problem (HCP).
Ans: Instance: an undirected graph G. Yes instance if there is an enumer- ation x0,x1,…,xk−1 of the nodes of G (all distinct) such that (xi,xi+1) is an edge (for i + 1 < k) and (xk−1,x0) is an edge of G. No instance otherwise.
The Hamiltonian Path Problem (HPP) is defined as follows. An instance of HPP is any undirected graph G. G is a yes-instance if it has a hamiltonian path, i.e. there is a sequence (n0,n1,...,nk) of nodes of G such that (i) every node of G occurs exactly once in the sequence and (ii) for i < k the pair (ni,ni+1) is an edge of G. If G has no hamiltonian path it is a no-instance of HPP.
3. Is every yes-instance of HCP also a yes-instance of HPP? Is every yes- instance of HPP also a yes-instance of HCP? Either prove the inclusion or provide a counter-example.
Ans: Every hamiltonian circuit is a hamiltonian path, hence the yes- instances of HCP are all yes-instances of HPP. But not every hamilto- nian path is a circuit, so take a graph with three nodes 0, 1, 2 and edges (01), (12) (since it is undirected, reverse edges are also included). It has a hamiltonian path (0,1,2) but no hamiltonian circuit, since (02) is not an edge. So it is a yes-instance of HPP but a no-instance of HCP.
4. Write down a non-deterministic algorithm that solves HPP and runs in p-time. Deduce that HPP ∈ NP.
{ Pick n∈G;
P ath = [n] while(|P ath| < |G|)
{ Pick m∈G\Path with (m,H(Path)) an edge of G; Let Path = [m : Path];
Note that in the while loop, if there is no node m to pick then the algorithm fails.
5. Define a polynomial-time reduction of HPP to HCP.
Ans: Important thing is that your reduction cannot work like this: “Let G be an instance of HPP. Let ρ be a hamiltonian path for G. Define G′ by connecting the two ends of ρ”. Nor “if G is a yes instance of HPP then ... else ...”. The reason is that we do not know if G is a yes or a no instance of HPP. As far as we know we cannot find out in polynomial time (unless P=NP). But your reduction is supposed to work in polytime.
I have the impression that answers to this question and the next one are now available on the web. Congratulations to those of you who managed to get their answers on their own.
Here’s my answer. Take an instance G of HPP. Define G′ from G by adding a single node n to G and adding a new edge (n,m) for each m ∈ G. This defines G′ and can be done in poly-time. This reduction is correct: If G has a hamiltonian path, p, then [n : p] is a hamiltonian circuit of G′. Conversely, if G′ has a hamiltonian circuit γ then, since you can start anywhere you like in a circuit, we can assume that γ starts from n, say γ = [n : γ′]. Then γ′ is a hamiltonian path for G.
6. Define a polynomial-time reduction of HCP to HPP.
Ans: LetGbeaninstanceofHCPandletEbethesetofedgesofG. Pick an arbitrary node g ∈ G. Define G′ by adding three new nodes to G, say u, v, w. Add the following edges to those of G: {(g, u), (v, w), (h, v) : (h, g) ∈ E}. This defined G′. If G has a ham. circuit γ then without loss g is the first node of γ. The last node of γ must be some neighbour h of g. So γ = [g,g1,g2,...,h]. Then [u,g,g1,g2,...,h,v,w] is a ham. path for G′. So if G is a yes instance of HCP then G′ is a yes instance of HPP. Conversely, suppose G′ is a yes instance of HPP. Let ρ be a ham. path for G′. The two ends of ρ must be u and w since these two nodes have only one edge connected to them. Also, the node next to w must be v since this is the only node connected to w. So ρ = [u,g,g1 ...,h,w,v] (or the same list reversed). Now h ∈ G is connected to w so by definition of G′, (g,h) ∈ E. Therefore [g,g1,...,h] is a ham. circuit for G and so G is a yes instance of HCP.
7. Assuming that HCP is NP-complete, prove that HPP is also NP-complete. 2
Ans: To prove that HPP is NPC we must prove (a) that HPP is in NP and (b) for all A ∈ NP we have A ≤p HPP. We proved (a) in question 4. For(b)letA∈NP.SinceHCPisNPCweknowthatA≤p HCP.In question 6 we showed that HCP ≤p HPP. By transitivity of ≤p it follows that A ≤p HPP, as required.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com