efficiencyIsBliss
efficiencyIsBliss

Reputation: 3093

Algorithms to find the number of Hamiltonian paths in a graph

I'm trying to solve a slightly modified version of the Hamiltonian Path problem. It is modified in that the start and end points are given to us and instead of determining whether a solution exists, we want to find the number of solutions (which could be 0).

The graph is given to us as a 2D array, with the nodes being the elements of the array. Also, we can only move horizontally or vertically, not diagonally. Needless to say, we can't go from one city to two cities because to do that we would need to visit a city twice.

I wrote a brute force solution that tries all 4 (3 or 2 for nodes on the edges) possible moves at each node and then counts the number of solutions (which is when it reaches goal and has seen all the other nodes too), but it ran for ridiculous amounts of time on inputs of modest size (like, say a 7x7 array).

I also thought of using bidirectional search since we know the goal, but this didn't really help, since we don't just want the fringes to meet, we want to also ensure that all the nodes have been visited. Moreover, it could be that when all nodes have been exhausted between the two fringes, they end in a way such that they can't be joined.

I feel like there is something I don't know that's leaving me with only a brute force solution. I know that the problem itself is NP-complete, but I'm wondering if there are any improvements over brute force. Can someone suggest something else?

--Edit--

I mentioned that using bidirectional search doesn't really help and I'd like to clarify why I thought so. Consider a 2x3 graph with the top left and bottom right nodes being the start and goal respectively. Let the fringes for bidirectional search move right from start and left from goal. After 2 moves, all the nodes would have been visited but there is no way to join the fringes, since we can only go in one direction from one node. However, it might be possible to make the algorithm work with some modifications, as David pointed out in his answer below.

Upvotes: 8

Views: 11178

Answers (6)

DavidErb
DavidErb

Reputation: 1

I found this approach to be extremely fast, and I was able to generalize it to work on a hexagonal grid: https://hal.archives-ouvertes.fr/hal-00172308/document. The trick is to push a frontier through the grid while keeping track of the possible paths. My implementation handles 20x20 grids in a few seconds.

Upvotes: 0

kkdrummer
kkdrummer

Reputation: 1

It can be solved using DP with bitmasking for values of n upto 20 or a few more i guess. Create a 2d dp table. dp[i][j] represents the answer of case that you are on ith vertex and j stores the information about visited vertices.Here's a C++ code.

Macros used:

#define    oncnt    __builtin_popcount
typedef    vector<int>   vi;

Outside Main:

vi ad[21];
 int n,m;

 int dp[20][(1<<19)+1];

int sol(int i,int mask)
{
    //cout<<i+1<<" "<<oncnt(mask)<<"\n";

    if(i==n-1)
    return 1;

    if(mask&(1<<i))
    return 0;

    int &x=dp[i][mask];
    if(x!=-1)
    return x;

    x=0;

    for(int j=0;j<ad[i].size();j++)
    {
        int k=ad[i][j];
        if(mask&(1<<k))
        continue;
        if(k==n-1&&oncnt(mask)!=n-2)
        continue;
        if(k!=n-1&&oncnt(mask)==n-2)
        continue;
// The above two pruning statements are necessary.
        x=madd(x,sol(k,mask|(1<<i)));

    }

    return x;

}

Inside Main:

cin>>n>>m;

for(int i=0;i<=n-1;i++)
 {
    for(int j=0;j<=(1<<(n-1));j++)
    dp[i][j]=-1;
 }


int a,b;
for(int i=1;i<=m;i++)
{
    cin>>a>>b;
    a--;
    b--;
    ad[a].pb(b);
}


 cout<<sol(0,0);

Upvotes: 0

MAK
MAK

Reputation: 26586

On a 7x7 array (i.e. a total of 7*7=49 nodes), having either a O(n!) algorithm or a O(2^n*n^2) algorithm will both take way too much time.

Perhaps there is some way speeding this up taking into account the special characteristics of this particular graph (e.g. each node has at most 4 edges), but a fast solution seems improbable (unless someone incidentally finds a polynomial time algorithm for the Hamiltonian Path problem itself).

Upvotes: 0

David Weiser
David Weiser

Reputation: 5195

You could still use a bidirectional search, just add a constraint to the search so that previously seen nodes will not be candidates for searching.

Another approach you could take which would lend itself to a paralellizable solution is to break the search into smaller searches.

For example, try to solve your original problem by solving:

For each node, n, which is not a start or end node, find all paths from the start to n (set1) and from n to the end (set2).

After you find set1 and set2, you can discard all elements of their cross product which have a common node other than node n.

Upvotes: 1

Gareth McCaughan
Gareth McCaughan

Reputation: 19971

Someone asked a question very similar to yours over on Math Overflow at https://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given-pair-of-vert and (1) they didn't get a deluge of "here's how to do it efficiently" responses (which probably means there isn't an easy way), (2) Mathematica apparently takes 5 hours to count the paths between opposite corners on a 7x7 grid, so you may well not be doing anything very wrong, and (3) there are a few interesting pointers among the answers.

Upvotes: 1

corsiKa
corsiKa

Reputation: 82559

According to Wolfram Alpha,

... the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

I believe you would want to start by finding a single hamiltonian path, and then splitting it into two paths, making the split point one that clearly separates the two paths as much as possible. Then you can find the permutations in the subgraphs (and recurse, of course!)

I don't know the exact algorithm, but that sort of divide and conquer method is where I would start.

Upvotes: 3

Related Questions