CODEWITHSUNDEEP
algorithmgraphgraph-theorynp-completehamiltonian-cycle
Garrett
Garrett

Reputation: 11725

Reduction algorithm from the Hamiltonian cycle

I believe that the Hamiltonian cycle problem can be summed up as the following:

Given an undirected graph G = (V, E), a Hamiltonian circuit is a tour in G passing through every vertex of G once and only once.

Now, what I would like to do is reduce my problem to this. My problem is:

Given a weighted undirected graph G, integer k, and vertices u, v both in G, is there a simple path in G from u to v with total weight of AT LEAST k?

So knowing that the Hamiltonian cycle problem is NP-complete, by reducing this problem to the Hamiltonian, this problem is also proved NP-complete. My issue is the function reducing it to Hamiltonian.

  1. The big issue is that the Hamiltonian problem does not deal with edge weights, so I must convert my graph to one that doesn't have any weights.
  2. On top of that, this problem has a designated start and finish (u and v), whereas the Hamiltonian finds a cycle, so any start is the same as the finish.

For (1), I am thinking along the lines of passing a graph with all simple paths of total weight LESS THAN k taken out. For (2), I am thinking that this is not really an issue, because if there is a Hamiltonian cycle, then the simple path from u to v can be sliced out of it.

So, my real questions are:

  1. Is my solution going to give me the right answer?
  2. If yes, then how can I take out the edges that will produce simple paths of total weight less than k WITHOUT affecting the possibility that one of those edges may be required for the actual solution? Because if an edge e is taken out because it produces a simple path of weight < k for a subset of E, it can still be used in a simple path with a different combination of edges to produce a path of weight >= k.

Thanks!

Upvotes: 2

Views: 8233

Answers (3)

Anders Lindahl
Anders Lindahl

Reputation: 42870

More of a hint than an answer:

A unweighted graph can be interpreted as a weighted graph where each edge has weight 1. What would the cost of a Hamiltonian cycle be in a graph like that?

Upvotes: 4

hugomg
hugomg

Reputation: 69934

The part about the mismatch between cycles and paths is correct and is a problem you need to solve. Basically you need to prove that the Hamiltonian Path problem is also NP complete (a relatively straightfoward reduction to the Cycle problem)

As for the other part, you are doing things in the wrong direction. You need to show that your more complicated problem can solve the Hamiltonian Path problem (and is thus NP-hard). To do this you just basically have to use the special case of unit-cost edges.

Upvotes: 2

Antti Huima
Antti Huima

Reputation: 25522

Your reduction is in the wrong direction. To show that your problem is NP-complete, you need to reduce Hamilton Circuit to it, and that is very easy. I.e. show that every Hamilton Circuit problem can be expressed in terms of your problem variant.

Upvotes: 6

Related Questions