Nice coarse-gaining based heuristic to partition the nodes into k sets of similar sizes minimizing the number of edges between those sets. Random maximal matchings are used to coarse-grain the graph. Maybe fast heuristics to obtain a large maximal matching can be considered, such as using the two rules detailed here: [Karp-Sipser based kernels for bipartite graph matching]( Publicly available implementation:
Maximimi at 2020-06-12 13:32:46
Edited by Maximimi at 2020-06-12 20:57:05

Please consider to register or login to comment on the paper.