[lorenzhs]

Not sure it's that easy. But parallel CH preprocessing has been done already, by finding sets of nodes that can be contracted independently (similar to your idea): http://algo2.iti.kit.edu/download/vetter_sa.pdf - the speedup wasn't too bad. Also, https://arxiv.org/abs/1208.2543