Hardness of crosstalk minimization in two-layer channel routing

Crosstalk minimization is one of the most important aspects of high-performance VLSI circuit design. With the advancement of fabrication technology, devices and interconnecting wires are being placed in close vicinity, and circuits are operating at higher frequencies. This results in crosstalk between adjacent wire segments. In this paper, it has been shown that the crosstalk minimization problem in the reserved two-layer Manhattan routing model is NP-complete, even if channels are free from all vertical constraints. It has also been demonstrated that it is hard to approximate the crosstalk minimization problem. Besides, the issue of minimizing bottleneck crosstalk has been introduced that is a new problem for crosstalk minimization. It has been proven that this problem is also NP-complete. It has been further shown that all these results hold even if doglegging is allowed.