1
$\begingroup$

I'll define the problems

UHAMPATH

Input: A undirected graph G and 2 nodes, s and t

Question: Is there a hamiltonian path from s to t in G?

UHAMCYCLE

Input: A undirected graph G

Question: Is there a hamiltonian cycle in G?

$$UHAMCYCLE \leq_p UHAMPATH$$

my reduction is as followed $(G) \to (G', s, t)$

function(G)

    for each e = (u, v) in E(G)
        G' = G
        add nodes u' and v' to G'
        add edges (u', u) and (v, v')
        s = u'
        t = v'
        if there is a hamilton path from s to t:
            return (G', s, t)

Basically if there is a hamilton cycle in G then some edge in $G$ will form a hamilton path in $G'$.

An example to further illustrate the reduction:

 Graph G

(a) ---- --(d)
 | \        |
 |   \      |
 |    \     |
 |     \    | 
 |      \   | 
 |       \  |
 |         \|      |
(b) ------ (c)

Has a clear Hamilton cycle (a, b, c, d). 

If we choose edges (a, d)

 Graph G'

(s)--(a) ---- --(d)
      | \        |
      |   \      |
      |    \     |
      |     \    | 
      |      \   | 
      |       \  |
      |         \|      
     (b) ------ (c)--(t)

Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)
      | \        |
      |   \      |
      |    \     |
      |     \    | 
      |      \   | 
      |       \  |
      |         \|      
     (b) ------ (c)

$(s \to a \to b \to c \to d \to t)$. Holds.


I'm confused whether or not I can use this line:

if there is a hamilton path from s to t:
    return (G', s, t)

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?

$\endgroup$
1
$\begingroup$

No. Since you are performing a many-one reduction, you have no capabilities beyond the model you are using for the reduction, in this case a poly-time Turing machine. Queries to the problem you are reducing to are only allowed if you are performing a Turing reduction, but that is a different notion and (strictly) more powerful than a many-one reduction (and is not what is used when establishing NP-completeness).

Of course, the line would be allowed if you managed to prove HAMPATH is solvable in polynomial time. I don't think you will be able to.

$\endgroup$

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.