Complete Weighted Schedule and Hamilton Tour

Question

I came across a question about a mid-term exam. Can someone clarify the answer?

Task A: Given the full weighted schedule of G, find a Hamilton tour with minimal weight.

Problem B: Given the full weighted graph of G and the real number R, does G have a Hamilton tour with a weight of at most R?

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

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

2) O (| E |) times

3) O (log m) times

4), because A is NP-Hard, this is not possible.

Answer 1

First algorithm

Answer (3) O(lg m) times . You just need to do a binary search for the minimum Hamilton tour in a weighted graph. Note that if there is a Hamiltonian tour along the length L in the graph, it makes no sense to check whether there is a Hamiltonian tour along the length L' , where L' > L , since you are interested in the Hamiltonian of the minimum weight of the tour. Thus, at each step of your algorithm, you can eliminate half of the remaining possible tours. Therefore, you will have to call B in your machine O(lg m) times, where m means the total weight of all the edges in the full graph.

---

Edit:

Second algorithm

I have a small modification of the above algorithm that uses machine O(|E|) times, as some people said that we cannot use binary search in an uncountable set of possible values ​​(and they are probably right): accept all possible subset of edges from the graph, and for each subset - a value that represents the sum of the weights of all the edges from the subset. Allows you to store values ​​for all subsets in an array named Val . The size of this array is 2^|E| . Sort Val in ascending order, and then apply binary search for the minimum path of the Hamiltonian, but this time call a machine that solves Problem B only with values ​​from the Val array. Since each subset of edges is included in the sorted array, it is guaranteed that a solution will be found. The total number of machine calls is O(lg(2^|E|)) , which is O(|E|) . So, the right choice is (2) O(|E|) times .

---

Note:

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

Answer 2

I believe that the choice that should have been the answer is that you cannot make. The reason is that you can only perform binary searches on countable sets.

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

However, you may be arbitrarily close to answer A in the log (n), but you cannot find the exact answer. (n is the size of the counting space).

Answer 3

Assuming that in the coding of graphs, weights are encoded as binary strings representing non-negative integers, and that Problem B can be solved algorithmically by entering a real number and performing calculations based on this, everything looks as follows.

You can perform the first binary search on the integral interval {0,...,M} to get the minimum weight of the Hamiltonian tour in O(log M) calls of the algorithm for Problem B As you know, the optimum is known, we can exclude single edges in G and use the resulting graph as an input for the algorithm for Problem B to check whether the optimal one changes or not. This process uses O(|E|) algorithm calls for Problem B to identify edges that occur in an optimal Hamiltonian tour. The total run time of this approach is O( (|E| + log M ) * r(G)) , where r(G) is the run time of the algorithm for Problem B with graph G as input. I believe r is a polynomial, although this is not explicitly stated in the question; in general, the total runtime will be polynomially limited in input coding length, since M can be calculated in polynomial time (and therefore pseudopolynomically limited in input coding length G ).

In this case, the proposed answers can be commented as follows.

• The answer is incorrect, since the set of necessary states is finite.
• It may be true, but does not follow from the algorithm described above.
• It may be true, but does not follow from the algorithm described above.
• The answer is incorrect. Strictly speaking, the NP-hardness of Problem A does not exclude the polynomial time algorithm; in addition, the algorithm for Problem B not considered polynomial, therefore, even P=NP does not follow if Problem A can be solved by the polynomial number of algorithm calls for Problem B (which is the case with the algorithm outlined above).