@sayan_paul: No your algo won’t work…If you consider the follwing test-case:
1
8 8
1 2
2 3
3 4
4 5
5 6
6 4
4 7
7 8.
This test case will answer YES however it does not have any Hamiltonian Path.
@xellos0: could you please look into my submission CodeChef: Practical coding for everyone. I used the Tutte Matrix concept. But it gave me wrong answer. I think somehow I am not setting the correct indeterminants of the Tutte Matrix. Please suggest what is the exact way to set the indeterminants. Thanks in advance.
@m_a_y_a , i used a similar approach , there is one more special case when you have no vertex of degree one (a cycle) - you just can’t plainly tell that if the cycle is of even length then the current component can be matched
Look at this case,
graph with 10 vertices and 12 edges,
[[1 2],[2 3],[1 3],[4 5],[5 6],[4 6],[7 8],[8 9],[7 9],[10 3],[10 5],[10 7]]
The answer is NO even though this graph has no vertices with degree 0 or 1 and has an even length (contains cycles), you can’t match this graph.
In order to solve it, i used this approach, found an articulation point in the cycle and associated it with any one of its adjacent edges having odd cycle length and disconnect the graph. Then again follow the entire algorithm from the start on the remaining graph. Worked Out !
@xellos0:I don’t understand… I simply calculated the determinant of the Tutte Matrix using Gaussian Elemination with random pivot technique.
How many times do I have to calculate the determinant??? Are you trying to say that I have to generate the Tutte matrix and calculate the determinant of each connected component seperately???
I’m not talking about connected components. Do you know what a randomized algorithm is? It’s something that can fail. The more test cases there are, the higher the chances of failing. The more times you try the same thing with different random values, the smaller the chance of failing. Maybe you just happened to choose the variables for which the determinant is 0, or maybe you just make a mistake somewhere
Can someone point me to a better explanation about the Blossom algorithm or to give an explanation of it applied to this problem? I really want to code it now
@sayan_paul My algorithm was to first eliminate all the leaf nodes using the steps mentioned by m_a_y_a above. Then You can use Dirac’s Theorem as you said above to detect Hamiltonian path
But in case of a cycle or many cycles if we take the vertex with the minimum degree(say A) and then find from the vertexes connected with it(A) the one with the minimum degree and make a pair with those two.
Is this approach correct, because the solution is getting accepted using this approach.
I always thought that setter/tester is watching submitted solutions (not all of course) and adds some tests, when he sees, that there are solution not intended to be accepted…
I used exactly the same approach as @ddhruvkr and got AC. And this algo is giving correct answer on both the test cases mentioned above…
Can anyone think of a test case where this algorithm fails??
@shangjingbo can you tell me how to construct the Tutte matrix for a given graph. If you say it is random then for the same two graphs matrix can be same. how do you resolve that ??. Thanks.
I used a similar approach.
I made a recursive function which took a source node and then if an edge existed with next node , then marked both vertices as visited. Then if(new source is available, i.e some unmarked vertex is present) recur with that node as source.
else if(no vertex is found that is unvisited) return true, i.e graph can be reduced
If one complete traversal results to no solution than backtrack(unmark the visited node and continue with the next one).
