I tried following strategy (though I never got it correct though later on applied on the edmond blossoms algorithm) for the problem SEAGRP in January Long Challenge 2014. Can anybody point out why is this algorithm incorrect?
- As I already know the graph I know the degree sequence of the graph(Obtained by removing multiple edges between same set of nodes as they don’t have any effect).
- The Final graph is a perfect matching so the degree sequence of each vertex in the resultant graph i s 1,1,1,1,…
- So If we subtract the degree sequence 1,1,1… from the degree sequence of the graph given we will get the degree sequence of the graph which needs to be subtracted from the original graph to make it a perfect matching.
- So on getting the degree sequence of the remaining graph I tried to prove it graphic by Havel Hakimi theorem.
Thank You.
1 Like
subtracting 1 from degree of a node means removing an edge joining to one of it’s neighbor. By removing this edge two nodes will get affected in their degrees but you are decreasing only one node’s degree that’s why this algo doesn’t work here…
Ex.
4 3
1 2
1 3
1 4
nodes 1 2 3 4
degree 3 1 1 1
If you decrease the degree of node “1” by one then you also have to decrease the degree of one of its neighbor bye one.
just check your algo for this example you will get the mistake.
The basic case is if there are odd number of vertices then perfect matching can’t be obtained. So if there are even number of vertices then only we proceed. Then in the example as you explained the original degree sequence of the graph is 3 1 1 1 and if there is a perfect matching of the graph then the degree sequence would be 1 1 1 1. Hence if degree sequence of the graph that needs to be deleted would have degree sequence of 2 0 0 0 which is not possible by havel-hakimi hence no perfect matching is possible.