Construct a graph containing a Hamiltonian path

2
votes

Background I am working on an optimization problem and have managed to reduce the problem to checking if a graph contains a Hamiltonian path. The reduced problem is as follows:

The problem We are given a sequence of edges (Example: e[1,5], e[3,4], ..., e[2,3]). We need to find the number of edges to take from the starting of this sequence so that the graph formed using these edges contains a Hamiltonian path. We also need to return the path.

My algorithm The problem can be solved by starting with a graph with no edges. We insert the edges one-by-one and check if the graph contains a Hamiltonian path in each iteration. This approach can be made somewhat faster by using the necessary condition for the existence of Hamiltonian paths. Still, the algorithm remains pretty inefficient.

The big question Is there a way this problem can be solved in a more efficient manner (perhaps by using the computation done in earlier iterations for speeding up later iterations)?

1
algorithmoptimizationgraph-theoryhamiltonian-cycle
Do you have more information on how step 2 is done? More specifically, how is the edge to be added chosen? - justhalf
How big N could be? Are there any estimations? - CaptainTrunky
@CaptainTrunky For now I am looking into problems where N is around 100 but I would eventually like to solve problems where N can be of the order of 10^4 - lakshayg
@justhalf Please see the edit I made to the question - lakshayg

1 Answers

0
votes

I would suggest using constraint satisfiability toolkit to solve this problem. I'll stick with Boolean satisfiability framework, but you can look at other options, e.g. SMT, integer programming.

Let's introduce a set of Boolean variables representing each vertex in a graph:

v_0, v_1, ..., v_N

Next, let's introduce a set of Boolean variables to represent each possible edge (N^2, obviously):

e_0, e_1, ..., e_{N^2}

Check this link for details.

A Boolean variable X is True if and only if corresponding vertex/edge are present in a graph. In your case, we are talking about edges.

At this moment, you can try introducing your edge-choosing algorithm as a set of Boolean constraints:

  1. if vertex v_i has degree D then edge E must be present
  2. if an edge between v_i and v_j is present then edge E must be absent
  3. etc

You can rely on pseudo-boolean encodings to introduce such constraints.

If there is such assignment to input variables that resulting Boolean formula returns True (it's is satisfied) then you can iterpret this assignment as a graph that contains Hamiltonian path AND it was built by given set of rules (constraints). You can use SAT solvers (e.g. Glucose to find such assignments.

I used similar approach to solve real-world problems with 10^5 variables and 10^6 constraints. It could be pretty time and memory consuming, but it works much better than brute-force and much more flexible: you can add/remove additional constraints easily without modifying your code.

I see a few drawbacks:

  1. This approach might be not so scalable in your case. Results heavily depend on a problem itself, so it's difficult to predict
  2. It's non-trivial task to encode your graph building procedure a set of Boolean constraints.
  3. Essentially, SAT solvers return random assignment. If you would like to see other solution/graph, you have to add new constraints to your problem.

My algorithm might be not perfect, but if you don't know exactly how to build a result (so there is no clear algorithm to do it, except for brute-force) constraint satisfiability toolkit is very efficient approach.

EDIT:

If a graph is weighted, you still can use SAT to solve this problem, but it will be much harder: weights should be within a given range and should be discrete. Still, you can consider mixed integer programming