The via minimization problem is NP-complete

The authors analyze the computational complexity of the constrained via minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists using only two layers. The authors first prove that the corresponding decision problem is NP-complete. They then show that it remains NP-complete even if one or more of the following restrictions are imposed: (1) the input layout must conform to a rectangular grid; (2) vias are restricted to lie at junctions which existed in the input layout; and (3) the maximum junction degree is limited to six or more.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>