The design of integrated circuits has achieved a
great deal of attention in the last decade. In the
routing phase, there have survived two open layout
problems which are important from both the
theoretical and the practical point of view. Up to
now, switchbox routing has been known to be solvable
in polynomial time when there are only 2-terminal
nets, and to be NP}-complete in case there exist
nets involving at least five terminals. Our main
result is that this problem is NP}-complete even if
no net has more that three terminals. Hence, from
the theoretical perspective, the SRP is completely settled.
The NP}-completeness proof is based on a reduction
from a special kind of the satisfiability
problem. It is also possible to adopt our
construction to channel routing which shows that
this problem is NP}-complete, even if each net does
not consist of more than five terminals. This
improves upon a result of Sarrafzadeh who showed the
NP}-completeness in case of nets with no more than
six terminals.
