The parallel complexity of minimizing column conflicts

Two-layer channel routers typically require a post-processing phase to reduce or eliminate column conflicts. Attempts have been made to parallelize this problem using local search heuristics that swap horizontal channel wire segments. The authors show that all such heuristics for this problem are P-hard and unlikely to be efficiently parallelizable