uzumaki_naruto_'s blog

How to find number of Hamiltonian paths between any 2 nodes of a unidirected graph?
By uzumaki_naruto_, history, 7 years ago, In English

Graph has 10 vertices.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Obviously we will have a certain number of eulerian paths between only one pair of vertices, as the degrees of the end vertices should be odd and all other degrees should be even. The problem now becomes to find the number of eulerian paths between fixed 2 vertices. Now let's add an edge between these two vertices. Well now the problem becomes to find the number of eulerian circuits in this new graph. Well it appears that the number of eulerian circuits as a problem is considered #P-complete, which means it still hasn't been solved. Are you sure your problem is that, or you missunderstood it?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I completely misunderstood the problem, We are given a graph of 10 vertices and we have to find number of "Hamiltonian" paths between any 2 vertices given by a matrix d[11][11]. What i think can be done is generate all permutations of [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and check if it is a valid path and if it is a valid path, increment d[first vertex][last vertex] but this approach times out. DFS also times out because the number of edges are huge. Edited the blog post

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well this approach is too slow. To solve the problem we first will fix the end vertices.

      Now consider the following dp:

      DP[first vertex][current vertex][visited vertices] = number of ways to reach this state from (first vertex, first vertex, only the first vertex is visited), were "visited vertices" is a bitmask of the visited vertices.

      Then the answer for a query (x, y) — x is the first vertex and y is the last one — is DP[x][y][ 2N - 1 ].

      The complexity will be which should be fast enough when N ≤ 10.

      → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you use a variation of traveling salesman you should be able to solve it in 2^N*N^3 You have dp[i][j][mask], where it means that you start in node i, want to end in node j and the 1s in the mask tell you which nodes you can visit.

→ Reply