Re: Discussion about transformation TSP to UniqueTSP


deepakc napisal(a):
deepakc wrote:
Radoslaw Hofman wrote:
Hi,

Does it make any difference? We can transform every NP problem to HC
and then build TSP with question PATH==N, that means that every NP
problem can be transformed to version having == in question.

In mine opinion <= is used to show that we are asking for optimal tour
instead of tour of size N, but it does not matter for me.

Cheers,
Radek Hofman

Hmmm, yes u're right !!
somehow it escaped me.

Dear Radek,

I had second thoughts, and now I think what you wrote above might be
wrong. The reason is suppose Mr. X gives me an original TSP and asks me
"Does there exist a TSP tour of length = 1000000", where I know for
certain that there cannot be such a tour, because 1000000 is > the sum
of the costs of all TSP Edges. In that case, I can confidently give a
NO answer to Mr. X, within Polynomial time (i.e. time for summing up
all Edge costs).

Hi,

General problem TSP is NP-complete. If we consider TSP problems where C
is greater then sum of weights then in fact we deal with different TSP
problem (simmilar to general but different) - this problem would be
easy (polynomially solvable). It is the same with SAT fro instance - if
we have instance of SAT where every variable is used only once then it
is polynomially solvable while general SAT is not (or being more
precise - is not known to be :).

So the Question is more difficult.....whether or not the YES/NO
Question is NP-Complete, actually depends on the value of C.

I would say that it corresponds to general TSP - if we modify
definition of problem then probabely we may obtain easy problem. Your
example may be even solvable in O(1) time :). If we consider set of
problems where we have set of weights and question "is there TSP tour
of overall cost equal to sum of weights" then following algorithm is
correct:

void main()
{
printf("NO\n");
}

But one thing is for certain....is that we cannot simply say "Convert
to HCP and then get a Question of whether there is tour of length = N".
That is most probably wrong, because it means that the problem is
difficult, though it is supposed to be easy in certain cases, like what
I showed above.

Eeeee - every problem (even with above question) may be transformed to
HCP. It is absolutely different thing if after transformation it will
still be easy (if we reduce 2SAT to HCP then we may (but may not)
obtain some easy subproblem of HCP - if we had 2 non-connected graphs
then answering question about HCP is as easy as above).

In summary - NP-completens is property of problem. If we add some extra
information we may refer to subproblem solvable even in O(1).

Best regards,

Radek Hofman

.

Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... TSP instance have a tour of cost <= C?"? ... I don't think it is possible to transform a TSP with multiple optima to ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... space (This is as per definition of NP-Complete Problems). ... And any HCP ... me an original TSP and asks me "Does there exist a TSP tour of length = ... time (i.e. time for summing up all Edge costs). ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... space (This is as per definition of NP-Complete Problems). ... And any HCP ... me an original TSP and asks me "Does there exist a TSP tour of length = ... time (i.e. time for summing up all Edge costs). ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... We can transform every NP problem to HC ... instead of tour of size N, but it does not matter for me. ... of the costs of all TSP Edges. ... within Polynomial time (i.e. time for summing up ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... Question is also NP-Complete, could you please let us know. ... lecture notes from MIT/Harvard/etc. ... We can transform every NP problem to HC ... In mine opinion <= is used to show that we are asking for optimal tour ...
    (comp.theory)