Complete Weighted Graph and Hamiltonian Tour

Question

I ran into a question on a midterm exam. Can anyone clarify the answer?

Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight.

Problem B: Given a Complete Weighted Graph G and Real Number R, does G have a Hamiltonian Tour with weight at most R?

Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.

1) We cannot do this, because there is uncountable state.

2) O(|E|) times

3) O(lg m) times

4) because A is NP-Hard, This is cannot be done.

Roseline

problem A is Traveling Salesman Problem – Rufena

I would guess that the intended answer was 2) O(|E|) times, by finding the optimum weight and then trying to remove each edge one by one to see which ones belong to an optimum tour, but this question is poorly constructed. – Deception

@DavidEisenstat exactly what I thaught when realizing it's "find the path" (and not only the cost), but that will be O(E+logM) – Rufena

@amit, i think, A is NP-hard and is TSP. B is Decision Problem of TSP and is NP-Complete. we have two method to solve A with B, 1- All permutation of vertex and all weights and check it with B. 2) search between numbers [0 to m]. this method maybe near to answer but with real weitghs maybe never reach to answer. (4) is false because also we cannot solve it with A in Poly time but using method 1 we can do it in O(n!), (2) and (3) is false bcause NP-HARd. the (1) is also not appropriate. – Roseline

Dear @DavidEisenstat please see. – Roseline

@Rufena O(log M) is sufficient to determine the exact optimum only if we assume integer weights, which who knows? O(|E|) information-theoretically is enough to determine the exact optimum, but I'm not sure what the actual algorithm would look like. This is more thought than this question deserves. – Deception

Please be more specific on how the edge weights are encoded. Are they encoded as nonnegative binary integers? How would R be encoded? Perhaps the original question from the exam is worded in a misleading way. – Lux

@Codor, maybe wrong. but is not given in the question. – Roseline

I somewhat second David Eisenstat - even supposing that the edge weightes are encoded binary nonnegative inegers, none of the given answers seems correct. – Lux

would you please add an answer with detail. would you please read fifth comments from top? thanks. @Lux – Roseline

@nini I have answered in detail, however my answer does not actually clarify the problem in an exhaustive way. Is the algorithm for Problem B a polynomial time algorithm or not? Whether answer 4 makes sense is dependent on this. – Lux

@amit, what do u think about new answers? – Roseline

@nini, NP or P is not a problem here, we only concern about whether we can transform A into B by a polynomial time algorithm. (3) seems to be a valid one, which Rontogiannis has pointed out in his answer. – Harrar

@PhamTrung see discussion in comments. His answer only yield approximation to the path's weight, and not the path itself – Rufena

@Rufena Taking into account your comment, I edited the answer by adding a second algorithm. I think it is correct now (although with the new algorithm the correct answer seems to be (2)) – Water

How is this a valid stackoverflow question? – Fearsome

Answer 1

First algorithm

The answer is (3) O(lg m) times. You just have to perform a binary search for the minimum hamiltonian tour in the weighted graph. Notice that if there is a hamiltonian tour of length L in the graph, there is no point in checking if a hamiltonian tour of length L', where L' > L, exists, since you are interested in the minimum-weight hamiltonian tour. So, in each step of your algorithm you can eliminate half of the remaining possible tour-weights. Consequently, you will have to call B in your machine O(lg m) times, where m stands for the total weight of all edges in the complete graph.

---

Edit:

Second algorithm

I have a slight modification of the above algorithm, which uses the machine O(|E|) times, since some people said that we cannot apply binary search in an uncountable set of possible values (and they are possibly right): Take every possible subset of edges from the graph, and for each subset store a value that is the sum of weights of all edges from the subset. Lets store the values for all the subsets in an array called Val. The size of this array is 2^|E|. Sort Val in increasing order, and then apply binary search for the minimum hamiltonian path, but this time call the machine that solves problem B only with values from the Val array. Since every subset of edges is included in the sorted array, it is guaranteed that the solution will be found. The total number of calls of the machine is O(lg(2^|E|)), which is O(|E|). So, the correct choice is (2) O(|E|) times.

---

Note:

The first algorithm I proposed is probably incorrect, as some people noted that you cannot apply binary search in an uncountable set. Since we are talking about real numbers, we cannot apply binary search in the range [0-M]

Water

We have discussed this idea already, it fails because (1) the OP is asking for the actual path, not only the weight. (2) You are not guaranteed to find the exact cost for real-valued (not integers) weight functions. – Rufena

please see yes/no formulation on seas.gwu.edu/~ayoussef/cs212/npcomplete.html – Roseline

see TSP formulation with Real number on: cs.utexas.edu/users/djimenez/utsa/cs3343/lecture22.html – Roseline

@nini I added a second algorithm which has a total non-polynomial complexity, but uses the machine O(|E|) times (answer (2)). Since there is no restriction about the algorithm's complexity, but only about the number of calls of the machine, I believe it is correct. – Water

Dear @RontogiannisAristofanis, are you here? – Roseline

@nini, How can I help you? – Water

now, i'm here, are u here @RontogiannisAristofanis. – Roseline

Would you please see, end of page. 2: after: Ex: TSP on weighted graph Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-choose-2. .............. in jn.inf.ethz.ch/education/script/chapter7.pdf – Roseline

@RontogiannisAristofanis, are u here? – Roseline

@nini I there something not clear in my answer? If there is, please inform me and i will explain it to you. – Water

why u didn't prefer to talk to me ? if your answer is right i want to approve it . @RontogiannisAristofanis – Roseline

@nini sorry, I was kind of busy lately. I checked the link you posted, but i couldn't understand the notation that was used, as I am still a high-school student and computer science is like a hobby to me. Anyway, I believe that the second algorithm I described is correct, because if the graph has real weights, then the binary search (described in the first algorithm) will have to continue for ever. I hope I helped :) – Water

@RontogiannisAristofanis, you read page 2 with Example of TSP ? – Roseline

Answer 2

I believe that choice that was meant to be the answer is 1- you can't do that. The reason is that you can only do binary search on countable sets.

Note that the edges of the graph may even have negative weights, and besides, they may have fractional, or even irrational weights. In that case, the search space for the answer will be the set of all real values less than m.

However,you may get arbitrarily close to the answer of A in Log(n) time, but you cannot find the exact answer. (n being the size of the countable space).

Jamille

Good points indeed; however we can suppose that some 'reasonable' encoding of the edge weights is chosen. – Lux

Answer 3

Supposing that in the encoding of graphs the weights are encoded as binary strings representing nonnegative integers and that Problem B can actually algorithmically be solved by entering a real number and perform calculations based on that, things are apparently as follows.

It is possible to do first binary search over the integral interval {0,...,M} to obtain the minumum weight of a Hamiltonian tour in O(log M) calls to the algorithm for Problem B. As afterwards the optimum is known, we can eliminate single edges in G and use the resulting graph as an input to the algorithm for Problem B to test whether or not the optimum changes. This process uses O(|E|) calls to the algorithm for Problem B to identify edges which occur in an optimal Hamiltonian tour. The overall running time of this approach is O( (|E| + log M ) * r(G)), where r(G) denotes the running time of the algorithm for Problem B taking a graph G as an input. I suppose that r is a polynomial, although the question does not explicitly state this; in total, the overall running time would be polynomially bounded in the encoding length of the input, as M can be computed in polynomial time (and hence is pseudopolynomially bounded in the encoding length of the input G).

That being said, the supposed answers can be commented as follows.

1. The answer is wrong, as the set of necessary states are finite.
2. Might be true, but does not follow from the algorithm discussed above.
3. Might be true, but does not follow from the algorithm discussed above.
4. The answer is wrong. Strictly speaking, the NP-hardness of Problem A does not rule out a polynomial time algorithm; furthermore, the algorithm for Problem B is not stated to be polynomial, so even P=NP does not follow if Problem A can be solved by a polynomial number of calls to the algorithm for Problem B (which is the case by the algorithm sketched above).

Lux

4. Is definitely wrong if for no other reason that being NP-hard doesn't mean it can't be done. I don't see anywhere in the question where they ask for a poly time algorithm to solve A (using B). – Stonedeaf

please see yes/no formulation on seas.gwu.edu/~ayoussef/cs212/npcomplete.html – Roseline