0
$\begingroup$

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.

Problem 2: Given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.

What is the polynomial-time reduction of problem 1 to problem 2?

Let TSP1 denote the following problem: given a TSP instance in which all edge costs are positive integers, compute the value of an optimal TSP tour. Let TSP2 denote: given a TSP instance in which all edge costs are positive integers, and a positive integer T, decide whether or not there is a TSP tour with total length at most T. Let HAM1 denote: given an undirected graph, either return the edges of a Hamiltonian cycle (a cycle that visits every vertex exactly once), or correctly decide that the graph has no such cycle. Let HAM2 denote: given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.

From Roughgarden's online algorithms course

The solution:

If TSP2 is polynomial-time solvable, then so is TSP1. If HAM2 is polynomial-time solvable, then so is HAM1.

$\endgroup$
  • $\begingroup$ How do you know a polynomial reduction is possible? Perhaps the source can help others find the answer. $\endgroup$ – ADdV Sep 29 at 19:31
  • $\begingroup$ Ok, I added the source. $\endgroup$ – Adam Tolnay Sep 29 at 19:38
  • 2
    $\begingroup$ This is called a search-to-decision reduction. You can find some examples, e.g. for 3SAT, under that name. A similar idea works here. $\endgroup$ – Lorenzo Najt Sep 29 at 20:01
  • $\begingroup$ I'll look into how it's done for 3SAT. $\endgroup$ – Adam Tolnay Sep 29 at 20:25
  • $\begingroup$ Please credit the original source of all copied or quoted material. Thank you! $\endgroup$ – D.W. Sep 29 at 20:28
1
$\begingroup$

First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky.

Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2).

algorithm for P1 with input G = (V,E):
  E' = {} # edges of "Hamilton Cycle"
  run subroutine for P2 on G
  if there is no Ham. Cycle:
    report that there is no Ham. Cycle
  for e in E:
    run P2 on (V,E - {e})
    if (V,E - {e}) contains "Hamilton Cycle":
      E <- E - {e}   # remove e
    else:
      E' <- E' + {e} # add e to cycle
  return E'

It uses the procedure for P2 $O(|E|)$ times, thus we obtained a polynomial reduction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not following. If there's no Hamilton Cycle then isn't E' = E? $\endgroup$ – Adam Tolnay Oct 1 at 12:47
  • 1
    $\begingroup$ @AdamTolnay The answer is now corrected. $\endgroup$ – plshelp Oct 1 at 20:24
  • 1
    $\begingroup$ I don't think this works... Maybe I'm misreading something, but for a triangle it just outputs all the edges except the first one. Also, I find it hard to believe that something like this wouldn't run into combinatorial issues, since it has to be correct for every permutation of the edges. This was the main problem I was running into when trying to come up with something polynomial. $\endgroup$ – Adam Tolnay Oct 2 at 15:36
  • 1
    $\begingroup$ You are right I messed up. I'll try to fix the algo. EDIT: ok I corrected the algorithm; $\endgroup$ – plshelp Oct 2 at 16:05
  • 1
    $\begingroup$ But if one of the outer edges is selected first and removed then there is no ham. cycle anymore. Thus the algorithm in its current form won't remove the outer edges of the square with the diagonal. see line 7,8,9. The if statement would go to "else" because the renoval of an outer edge would destroy the cycle. $\endgroup$ – plshelp Oct 2 at 20:10

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.