8
$\begingroup$

I ran into a question on previous Mid-Exam. anyone could clarify me?

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, Is G has a Hamiltonian Tour with weight at most R?

Suppose there is a machine that solves B. with how many times call of B (each time G and Real number R are given), We Can 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.
$\endgroup$
  • $\begingroup$ In $O(lg$ $ M)$ steps you will have a very good estimate about the weight of the minimal Hamiltonian tour, however even after knowing this it is NP hard to find the tour. So my guess would be (4). But I have no idea about (1). But definitely not (2) or (3). $\endgroup$ – user67773 Feb 20 '15 at 3:57
  • $\begingroup$ How are given then inputs of the problem ? real numbers are infinite by definition, so how they are encoded ? $\endgroup$ – Xoff Feb 26 '15 at 21:36
  • $\begingroup$ @Xoff gave a proof of what I stated in the comment of your answer. If you have any idea on how to find the minimal weight we are done :D $\endgroup$ – wece Feb 26 '15 at 21:41
  • $\begingroup$ I'm convinced now that it depends of the way your reals are encoded. If they are encoded naively, the problem is the same as with integers, and solution 2 seems good to me as wece explained it. If they are true reals, even computable one enumerated by some kind of finite machine, this can't be done (but not because of the uncountable states, more a computability problem) $\endgroup$ – Xoff Feb 26 '15 at 22:05
  • $\begingroup$ Note that this question is not well formulated. Because you can solve $A$ without any call to $B$. $\endgroup$ – Xoff Mar 3 '15 at 13:53
1
$\begingroup$

This is not an answer, I just needed more space than in the comment to follow my discussion with Xoff

I'm just showing here that if you know the minimal weight $R_m$ of an Hamiltonian cycle, you can effectively build one of weight $R_m$ using $|E|$ calls to B.

I assume here that all the weight are positive.

I denote here $B(G,w,R)$ the call of $B$ on $G$ with weight function $w$ and bound $R$.

Let $\{e_1,...,e_n\}$ be the edges of the graph $G$.

Consider the weight function $w_1$ such that $w_1(e_1)=w(e_1)+R_m$ and $w_1(e_i)=w(e_i)$ for $i\neq 1$.

If $B(G,w_1,R_m)$ is false we mark $e_1$.

More generally we define $w_k$ as $w_k(e_k)=w_{k-1}(e_k)+R_m$ and $w_k(e_i)=w(e_i)$ if $e_i$ is marked and for $w_k(e_i)=w_{k-1}(e_i)$ otherwise.

Again if $B(G,w_k,R_m)$ is false we mark $e_k$.

At the end all the edges marked belong to a cycle of weight $R_m$.

$\endgroup$
  • $\begingroup$ I think this is a good idea but : 1. No edge can be marked if there are several minimal Hamiltonian cycles such that no edge is used by all of them. 2. Computing the minimal weight can be impossible in finite time if we consider the fact that we are using true reals, and that even a dichotomy never ends $\endgroup$ – Xoff Feb 26 '15 at 21:45
  • $\begingroup$ @wece, please update your answer, complete it. to set bounty for you, bounty expire on 1 days. $\endgroup$ – Ali Movagher Feb 27 '15 at 16:47
  • $\begingroup$ @Xoff for 1: the fact that there are several minimal Hamiltonian cycles is not a problem in the algorithm I gave we modify the weight in a way such that the number of minimal cycle decrease. Indeed if an edge $e_i$ belongs to a minimal cycle and not to an other the edge will not be marked (since $B(G,w_i,R)$ is true because of the other cycle) and for the following the first cycle will never be considered again since the weight of $e_i$ is still set to $w(e_i)+R$. $\endgroup$ – wece Feb 27 '15 at 17:16
  • $\begingroup$ @Xoff for 2: i agree it may be impossible. But may be it is possible :) $\endgroup$ – wece Feb 27 '15 at 17:17
  • $\begingroup$ @AliMovagher Sadly I cannot complete my answer ... I have no idea of how to compute the minimal value. As I said to Xoff I don't even know if it is possible. $\endgroup$ – wece Feb 27 '15 at 17:18
0
$\begingroup$

Real numbers can not be manipulated by machines : they have infinite size and you can't even answer such a simple question as $$x=y$$ on real numbers in finite time.

Having a machine $B$ that deals with infinite input is quite strange (It output a single bit however). How do you give the input to $B$ ? How do you manipulate the input ?

I think the question is not ok due to this problem. So I would answer 1 : We cannot do this, because there is uncountable state. But it's not really satisfying, it really depends of what's thoughts were in the teacher mind when he wrote the question.

Any reals manipulation in computability must be well defined (are they floating numbers, are they computable reals defined by an algorithm, are they infinite list of digits or are they defined by infinite closed intervals like continued fractions). Depending of definitions, you can or can't do some basic things like compare or add numbers. Without proper definition, we can only assume the worst, and we can't manipulate them.

$\endgroup$
  • $\begingroup$ I agree with you. But the problem start with "Suppose there is a machine that solves B", so even if this machine cannot exists the question is still valid, and still interesting. With such machine B it's not even sure that you need to manipulate real to answer A, may be just change the weight function by setting edges to 0 or m would be enough ... $\endgroup$ – wece Feb 27 '15 at 17:10
  • $\begingroup$ @wece : yes, but how do you set an edge to some value ? You need to manipulate an infinite input to do that. That's quite strange ! For example you can solve the halting problem using $B$... $\endgroup$ – Xoff Feb 27 '15 at 17:15
  • $\begingroup$ I agree it's pretty strange but if you find a good representation you may need to manipulate only a finite prefix of your infinite input to get the input you need to B. But hte not really the point of the question here I think. I this question assume that you can manipulate real (like doing addition, multiplication, comparisons ...) in constant time. But even with that finding the minimal value is a pain ... $\endgroup$ – wece Feb 27 '15 at 17:32
  • $\begingroup$ please see see TSP formulation with Real number on: cs.utexas.edu/users/djimenez/utsa/cs3343/lecture22.html $\endgroup$ – Ali Movagher Mar 3 '15 at 12:09
  • $\begingroup$ @AliMovagher This is not nice to use the term real and then explain we use rational numbers. They should use rational numbers from start. Please, update your question to reflect the fact that real number means rational number in this context. $\endgroup$ – Xoff Mar 3 '15 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.