Matching Problems II

A typically uninteresting week and a half since my last post, and not a lot of results to show for it unfortunately. I have spent the time attempting to resolve an issue with multi-matching algorithm, but to no avail.

Analysis of the processes (and when I say processes I mean the hundreds and thousands of lines of information output at each stage of the coarsening scheme) showed that the cause comes from minute decisions when choosing matchings. It appears as though these decisions come from the method of storing adjacent vertices within each vertex as opposed to a set of edges - and will only occur in large graphs with many levels (graphs over 20k vertices normally present with more levels in the multilevel scheme).

Attempted fixes did little to fix the issue (but did result in a more efficient coarsening algorithm - thank you hash maps!).

In any case, I suspect my methodology is flawed as I am iterating over vertices normally - it gives vertices at the beginning more chance of being matched whereas though near the end will have less available partners. For now, I need to check with my supervisor's previous work in order to determine whether the number of coarser levels is comparable, or whether it is some part of my code that is giving bad answers.

As a break away from problem solving, I intend to spend the rest of this week on the new matching and pre-processing techniques (using only standard edge contraction - known to work as expected). This will enable me to play around with some of the ideas and get some preliminary results.

Interesting thought for the day - it seems finan512, a ring of repeated groupings of vertices, does not actually coarsen to a ring in any of my coarsening. Instead, reducing to a sparse type graph. Looking at the structure makes me think that if I were to identify these repeated vertex groupings, I could provide layout for one and then just replicate the same layout around the circumference of the ring. This is a play on identifying automorphisms[?] within the graph and placing them in appropriate locations as suggested long ago by Lipton et al. It is a bit biased to just the finan512 graph, but if they could be identified with ease in any graph - would it help? not really my concern at the moment, but food for thought.