% The Chicago Journal of Theoretical Computer Science, Volume 1996, Article 6
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1996 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,published]{cjstruct}
\else
\documentclass[v1.1,published]{cjstruct}
\fi
%
%\usestyleresource{epsf}
\usestyleresource{amstex}
\usestyleresource{epic}
\usestyleresource{eepic}
%
% Local macro definitions for this article.
%
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textmd}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textsc}[1]{{\sc #1\/}}\fi
\ifltwoe\else\newcommand{\textrm}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\mathcal}[1]{{\cal #1\/}}\fi
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\catcode`\@=12
%
\newcommand{\textuprm}[1]{\textup{\textrm{#1}}}
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
\newcommand{\exampfontshape}{\fontshape{n}\selectfont}
%
\newcommand{\figlabel}[1]{(#1)}
%
\mathstyleclass{\complexityclass}{\mathord}{\textuprm}
%
\newcommand{\setofsupernets}[1]{\mathcal{#1}}
%
\newcommand{\setof}[2]{\{\,#1\mid#2\,\}}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\oftype}{\colon}
\newcommand{\unionofset}[2]{\bigcup_{#1}#2}
\newcommand{\setunion}{\cup}
\newcommand{\problemlabel}[1]{\textmd{\textsc{#1}}}
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
%
% Macros for the editors' comment
%
% The cross symbol indicates a recently deceased editor.
%
\ifx\deceased\undeftex
  \newcommand{\deceased}[1]{\dag#1}
\fi
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1996, Article 6\\
      \textit{30 December 1996}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142 USA; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{gopher.mit.edu}
    \item \emph{gopher.cs.uchicago.edu}
    \item anonymous \emph{ftp} at \emph{mitpress.mit.edu}
    \item anonymous \emph{ftp} at \emph{cs.uchicago.edu}
  \end{itemize}
  \sentence
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert,\registered
  SciSearch,\registered Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered}
}
%
\copyrightstmt{%
  \copyright 1996 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The \emph{Chicago Journal of Theoretical Computer Science}
  is a peer-reviewed scholarly
  journal in theoretical computer science\@. The journal is committed
  to providing a forum for significant results on theoretical
  aspects of all topics in computer science\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Ted Herman & Michael Merritt \\
        Jin-Yi Cai & Steve Homer & Alan Selman \\
        Anne Condon & Neil Immerman & Nir Shavit \\
        Cynthia Dwork & \deceased{Paris Kanellakis} & Eva Tardos \\ 
        David Eppstein & Howard Karloff & Sam Toueg \\
        Ronald Fagin & Philip Klein & Moshe Vardi \\
        Lance Fortnow & Phokion Kolaitis & Jennifer Welch \\
        Steven Fortune & Stephen Mahaney & Pierre Wolper
      \end{tabular}
    \vspace{1ex}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
\pagebreak[0]
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1996}
%
\articleid{6}
%
\selfcitation{
     @article{cj96-06,
       author={Martin Middendorf},
       title={Manhattan Channel Routing is NP-Complete under Truly
         Restricted Settings},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1996},
       number={6},
       publisher={MIT Press},
       month={December},
       year={1996}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Manhattan Channel Routing is NP-Complete under Truly Restricted
  Settings}
\shorttitle{Manhattan Channel Routing}
%
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Martin Middendorf}
   \collname{}{Middendorf, Martin}
   \begin{institutioninfo}
       \instname{Universit\"at Karlsruhe}
       \department{Institut f\"ur Angewandte Informatik und Formale
         Beschreibungsverfahren}
       \address{}{Karlsruhe}{}{Germany}{D-76128}
   \end{institutioninfo}
   \email{middendorf@aifb.uni-karlsruhe.de}
\end{authorinfo}
%
\shortauthors{Middendorf}
%
\begin{editinfo}
  \submitted{11}{12}{1994}\reported{12}{3}{1996}
  \submitted{13}{3}{1996}\reported{5}{11}{1996}
  \submitted{6}{11}{1996}\published{30}{12}{1996}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
%
\apar{Abstract-1}
Settling an open problem that is over ten years old, we show that
Manhattan channel routing---with doglegs allowed---is
\(\complexityclass{NP}\)-complete when all nets have two terminals\@.
This result fills the gap left by Szymanski \cite{cj96-06-09}, who
showed the \(\complexityclass{NP}\)-completeness for nets with four
terminals\@. Answering a question posed by Schmalenbach
\cite{cj96-06-08} and Greenberg, J\'aj\'a, and Krishnamurty
\cite{cj96-06-04}, we prove that the problem remains
\(\complexityclass{NP}\)-complete if in addition the nets are
single-sided and the density of the bottom nets is at most one\@.
Moreover, we show that Manhattan channel routing is
\(\complexityclass{NP}\)-complete if the bottom boundary is
irregular and there are only \(2\)-terminal top nets\@. All of our
results also hold for the restricted Manhattan model where doglegs
are not allowed\@.
%
\end{abstract}
%
\asection{1}{Introduction}
%
\apar{1-1}
The channel-routing problem is a basic problem in the layout design of
VLSI circuits\@. A channel consists of a rectilinear grid with top and
bottom boundaries\@. A (\(k\)-terminal) net is a set of (\(k\))
terminals that are located at grid points on the boundaries\@. The
channel-routing problem is to find, for a given set of nets, a set of
edge-disjoint subgraphs of the grid connecting the terminals of the
nets, while minimizing the number of horizontal lines (tracks)\@. There
are additional possible restrictions that are important in practice\@.
We can restrict the number of terminals in a net (two terminals is the
simplest subcase, and it does arise in applications), and whether the
nets are single-sided (all terminals of a net lie on the same
boundary)\@. The status of these restricted problems is discussed below\@.
%
\apar{1-2}
The routing subgraphs consist of horizontal and vertical segments\@. In
the Manhattan model, all the horizontal segments of the routing
subgraphs are assigned to one layer, and all the vertical segments to
another layer\@. Connections between horizontal and vertical segments
are made via holes\@. No two segments of the same layer are allowed to
share a common grid point\@. Thus, segments may cross only if they are
on different layers\@. We also consider a restricted version of this
general Manhattan model\@. In the restricted (dogleg-free) Manhattan
model, no routing subgraph for a net is allowed to have more than one
horizontal segment (i.e., doglegs are not allowed)\@.
%
\apar{1-3}
It has been shown by LaPaugh \cite{cj96-06-05} that the decision
version of the dogleg-free Manhattan channel-routing problem is
\(\complexityclass{NP}\)-complete, even when all nets have only two
terminals\@. This result has been independently extended by
Schmalenbach \cite{cj96-06-08} and Greenberg, J\'aj\'a, and
Krishnamurty \cite{cj96-06-04}\@. They showed that restricted Manhattan
channel routing with \(2\)-terminal nets is
\(\complexityclass{NP}\)-complete even when all nets are single-sided
(i.e., both terminals lie on the same boundary)\@.
%
\begin{sloppypar}
\apar{1-4}
The general Manhattan channel-routing problem---where doglegs are
allowed---seems harder to analyze, and its complexity is not well
understood\@. Szymanski \cite{cj96-06-09} showed that the general
Manhattan channel-routing problem is \(\complexityclass{NP}\)-complete
even if all nets have at most four terminals\@. He claimed that his
proof can be extended to show that the problem remains
\(\complexityclass{NP}\)-complete if all nets have only two terminals\@.
Unfortunately, he did not provide a proof of this claim, and it is not
clear how to extend Szymanski's technique to handle this case\@. In
fact, Schmalenbach \cite{cj96-06-08} and Greenberg, J\'aj\'a, and
Krishnamurty \cite{cj96-06-04} stated that it is an interesting open
problem whether Manhattan channel routing with \(2\)-terminal,
single-sided nets is also \(\complexityclass{NP}\)-complete in the
general model, where doglegs are allowed\@. In this paper, we solve this
problem and close the gap left by Szymanski\@. We show that Manhattan
channel routing is \(\complexityclass{NP}\)-complete when all nets are
single-sided, \(2\)-terminal nets and doglegs are allowed\@. Our result
holds even when we further assume the bottom nets have density one\@.
This is somewhat surprising, since the ``slightly'' simpler problem of
routing single-sided nets with possibly more than two terminals to
only one boundary is polynomially solvable\@. Our proof is easier than
that of Szymanski, and and we believe that it gives a good insight as
to why routing in the Manhattan model is difficult\@. Moreover, the
case that all nets are two-sided is investigated\@. We show that general
Manhattan channel routing is \(\complexityclass{NP}\)-complete when
all nets are two-sided, \(2\)-terminal nets, even when each net has
its left terminal on the bottom boundary and its right terminal on the
top boundary\@.
\end{sloppypar}
%
\apar{1-5}
All of our results also hold in the restricted Manhattan model\@. Thus,
by showing that Manhattan channel routing with single-sided,
\(2\)-terminal nets is \(\complexityclass{NP}\)-complete when doglegs
are not allowed and the bottom nets have density one, we have extended
the results of Schmalenbach and Greenberg, J\'aj\'a, and Krishnamurty\@.
%
\apar{1-6}
Comparing Manhattan channel routing with knock-knee routing (where the
nets are allowed not only to cross at a grid point, but also to form a
knock-knee [see Figure~1], i.e., to bend away from each other
\cite{cj96-06-06}), our results show that Manhattan channel routing is
the harder problem (unless
\(\complexityclass{P}=\complexityclass{NP}\))\@. It is known that
knock-knee routing is polynomial time solvable for \(2\)-terminal nets
\cite{cj96-06-01}, \cite{cj96-06-02}, whereas it is shown in this paper
that general Manhattan channel routing is an
\(\complexityclass{NP}\)-complete problem even for very restricted
sets of \(2\)-terminal nets\@. For nets with a larger number of
terminals, knock-knee routing becomes
\(\complexityclass{NP}\)-complete too\@. (It is
\(\complexityclass{NP}\)-complete for \(5\)-terminal nets
\cite{cj96-06-07}\@. The complexity for \(3\)-terminal and
\(4\)-terminal nets is open\@.)
%
\begin{figure*}
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
\fbox{%
%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(963,984)(0,-10)
\thicklines
\put(637.500,643.500){\arc{318.198}{1.7127}{2.9997}}
\path(615,486)(930,486)
\put(325.500,325.500){\arc{318.198}{4.8543}{6.1413}}
\path(348,483)(33,483)
\path(482,348)(482,33)
\thinlines
\path(437,484)(527,484)
\path(482,529)(482,439)
\thicklines
\path(480,621)(480,936)
\end{picture}
}
%
}
\end{center}
%
\afigcap{1}{A knock-knee}
\end{figure*}
%
\apar{1-7}
Our proof technique is also used to show that a quite restricted case
of routing in a channel where one boundary is slightly irregular is
\(\complexityclass{NP}\)-complete\@. Note that this means that all
practical cases which include our case are
\(\complexityclass{NP}\)-complete too\@.
%
\apar{1-8}
In Section~2, we introduce some notation and another channel-routing
problem as a preparation of our main results\@. In Section~3, we show
the \(\complexityclass{NP}\)-completeness of this problem\@. Minor
modifications of this proof yield proofs of our results about the
complexity of Manhattan channel routing\@. In Section~4, we give our
result for routing in a channel with an irregular boundary\@.
%
\asection{2}{Preliminaries}
%
\apar{2-1}
A channel with a \emph{right boundary} consists of a rectilinear grid
that has boundaries at three sides, namely, the top boundary, the
bottom boundary, and the right boundary\@. The horizontal grid lines
between the top and the bottom boundaries are called \emph{tracks}\@.
They are numbered \(1,\dots,k\) from the topmost track to the
bottommost track\@. The vertical grid lines (including the right
boundary) are the \emph{columns}\@. Columns are numbered from left to
right, with the right boundary at column~\(p\)\@.
%
\apar{2-2}
A \emph{\(2\)-terminal net} consists of two \emph{terminals} located
at grid points on the boundaries\@. All the nets we deal with in this
paper are \(2\)-terminal nets, so we often omit the term
``\(2\)-terminal\@.'' Throughout, we assume that the terminals of a net
are in different columns\@. In our model, terminals on the right
boundary are movable in the vertical direction\@. No two terminals can
be on the same grid point\@. A net with terminals in columns \(a\) and
\(b\) (\(a<b\)) \emph{starts} at \(a\) and \emph{terminates} at \(b\)\@.
A net is a \emph{top} (respectively \emph{bottom}) \emph{net} if it
starts at the top (respectively bottom) boundary and terminates at the top
(respectively bottom) boundary or at the right boundary\@. It is denoted by
\((a,b)_{t}\) (respectively \((a,b)_{b}\))\@. If we do not want to specify the
type of a net, i.e., whether it is a top or bottom net, we omit the
index \(t\) or \(b\), respectively\@. A net is \emph{single-sided} if
it is a top or bottom net\@.
%
\apar{2-3}
A \emph{supernet} \(N\) for a channel with the right boundary at
column \(p\) is a set of nets
\(\setof{(a_{i},b_{i})_{x_{i}}}{i\in[1:r]\mbox{, }x_{i}\in\{t,b\}}\)
with \(a_{1}<b_{1}<a_{2}<b_{2}<\dots<a_{r}<b_{r}\leq p\)\@. A supernet
\emph{starts} (respectively \emph{terminates}) at a column if it contains a
net that starts (respectively terminates) at this column\@. A supernet is
\emph{single-sided} if all of its nets are single-sided\@.
%
\apar{2-4}
For a set of nets \(M\), the \emph{local density} at column \(q\) is
the number of nets in \(M\) of the form \((a,b)\) with \(a\leq q\leq b\)\@.
The \emph{density} of \(M\) is the maximum of the local densities over
all columns\@.
%
\apar{2-5}
Let \(\setofsupernets{N}\) be a set of single-sided supernets for a
channel with \(k\) tracks and a right boundary at column \(p\)\@. A
\emph{routing} for \(\setofsupernets{N}\) is an arrangement of routing
paths in the channel for all the nets contained in the supernets in
\(\setofsupernets{N}\) with respect to the Manhattan model\@. Let
\(\setofsupernets{N}'\subset\setofsupernets{N}\) be the set of those
supernets in \(\setofsupernets{N}\) containing a net with a terminal
on the right boundary\@. An injective function
\(f\oftype\funcspace{\setofsupernets{N}'}{[1:k]}\) is called an
\emph{assignment function} for \(\setofsupernets{N}\)\@. An assignment
function is \emph{feasible} if there exists a routing for
\(\setofsupernets{N}\) such that for each supernet
\(N\in\setofsupernets{N}'\), the terminal on the right boundary of
\(N\) is placed on track \(T_{f(N)}\)\@.
%
\begin{alabsubtext}{Example}{1}{}
Consider the set \(\setofsupernets{N}=\{N_{1},N_{2},N_{3},N_{4}\}\)
of single-sided supernets for a channel with four tracks and a right
boundary at column \(7\) where \(N_{1}=\{(1,7)_{t}\}\),
\(N_{2}=\{(1,3)_{b},(6,7)_{t}\}\),
\(N_{3}=\{(2,4)_{t},(5,7)_{b}\}\), \(N_{4}=\{(3,7)_{t}\}\)\@. Two
possible routings for \(\setofsupernets{N}\) are given in Figure~2\@.
\end{alabsubtext}
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5087,1995)(0,-10)
\path(495,1692)(2070,1692)(2070,567)(495,567)
\dashline{50.000}(495,1467)(720,1467)
\dashline{60.000}(495,1242)(945,1242)
\dashline{60.000}(1395,1242)(1620,1242)
\dashline{60.000}(495,1017)(1170,1017)
\dashline{50.000}(495,792)(720,792)
\dashline{60.000}(1170,792)(1845,792)
\dashline{50.000}(1845,792)(1845,567)
\dashline{60.000}(1620,1692)(1620,1252)
\dashline{60.000}(1395,1252)(1395,567)
\dashline{50.000}(1170,1017)(1170,792)
\dashline{60.000}(945,1252)(945,567)
\dashline{60.000}(720,1467)(720,792)
\path(3195,1692)(4770,1692)(4770,567)(3195,567)
\dashline{60.000}(3195,1467)(3870,1467)
\dashline{60.000}(3195,1242)(3645,1242)
\dashline{60.000}(4095,1242)(4545,1242)
\dashline{50.000}(3195,1017)(3420,1017)
\dashline{50.000}(3195,792)(3420,792)
\dashline{60.000}(3870,792)(4320,792)
\dashline{60.000}(4545,1242)(4545,567)
\dashline{60.000}(4320,1692)(4320,792)
\dashline{60.000}(4095,1242)(4095,567)
\dashline{60.000}(3870,1467)(3870,792)
\dashline{60.000}(3645,1242)(3645,567)
\dashline{50.000}(3420,1017)(3420,792)
\put(630,1800){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\put(630,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(1080,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(1530,342){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(2160,747){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(2160,972){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(2160,1197){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(855,1800){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(1080,1800){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(1305,1800){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(1755,1800){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(3330,1800){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\put(3330,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(3780,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(4230,342){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(3555,1800){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(3780,1800){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(4005,1800){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(4455,1800){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(4860,747){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(4860,972){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\put(4860,1197){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(4860,1422){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(0,27){\makebox(0,0)[lb]{\smash{column}}}
\put(675,27){\makebox(0,0)[lb]{\smash{\(1\)}}}
\put(900,27){\makebox(0,0)[lb]{\smash{\(2\)}}}
\put(1080,27){\makebox(0,0)[lb]{\smash{\(\dots\)}}}
\put(2025,27){\makebox(0,0)[lb]{\smash{\(7\)}}}
\put(2700,27){\makebox(0,0)[lb]{\smash{column}}}
\put(3375,27){\makebox(0,0)[lb]{\smash{\(1\)}}}
\put(3600,27){\makebox(0,0)[lb]{\smash{\(2\)}}}
\put(3780,27){\makebox(0,0)[lb]{\smash{\(\dots\)}}}
\put(4725,27){\makebox(0,0)[lb]{\smash{\(7\)}}}
\put(2160,1422){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\thicklines
\path(720,1692)(720,1467)(2070,1467)
\path(945,1692)(945,1242)(1395,1242)(1395,1692)
\path(1170,1692)(1170,1017)(2070,1017)
\path(720,567)(720,792)(1170,792)(1170,567)
\path(1620,567)(1620,1242)(2070,1242)
\path(1845,1692)(1845,792)(2070,792)
\path(3420,1692)(3420,1017)(4770,1017)
\path(3645,1692)(3645,1242)(4095,1242)(4095,1692)
\path(3870,1692)(3870,1467)(4770,1467)
\path(4545,1692)(4545,1242)(4770,1242)
\path(3420,567)(3420,792)(3870,792)(3870,567)
\path(4320,567)(4320,792)(4770,792)
\end{picture}
}
\end{center}
%
}}
\afigcap{2}{Two routings for supernets \protect\(N_{1},\dots,N_{4}\protect\)}
\end{figure*}
%
\apar{2-6}
Our problem can now be formulated as follows\@.
%
{\nopagebreakbeginpar
\begin{sloppypar}
\begin{alabsubtext}{Definition}{1}{Channel Routing with Right Boundary}
%
\ \par
\begin{description}
%
\item[\problemlabel{Instance:}] A triple
\(I=(k,p,\setofsupernets{N})\) with integers \(k,p\) and a set
\(\setofsupernets{N}=\{N_{1},N_{2},\dots,N_{k}\}\) of \(k\)
single-sided supernets for a channel with \(k\) tracks and a right
boundary at column \(p\)\@.
%
\item[\problemlabel{Question:}] Is there a routing for \(I\), i.e.,
does there exist a feasible assignment function for
\(\setofsupernets{N}\) in a channel with \(k\) tracks and right
boundary at column~\(p\)\@?
%
\end{description}
%
\end{alabsubtext}
\end{sloppypar}}
%
We abbreviate this problem as CRRB\@.
%
\apar{2-7}
Let \(I=(k,p,\setofsupernets{N})\) be an instance of CRRB\@. An
\emph{extension} of \(I\) is an instance
\(I'=(k,q,\setofsupernets{N}')\) with \(q>p\) and
\(\setofsupernets{N}'=\{N_{1}',N_{2}',\dots,N_{k}'\}\) such that for
all \(i\in[1:k]\), the following hold:
%
\begin{enumerate}
\item[1.] For all \((a,b)_{x}\) with \(b<p\), \(x\in\{b,t\}\), we have
  \((a,b)_{x}\in N_{i}\) if and only if \((a,b)_{x}\in N_{i}'\)\@.
\item[2.] If \(N_{i}\) contains a net of the form \((a,p)_{x}\),
  \(x\in\{b,t\}\), then \(N_{i}'\) contains a net of the form
  \((a,p')_{x}\) for a \(p'\) with \(p<p'\leq q\)\@.
\end{enumerate}
%
\apar{2-8}
To simplify the notation, we will denote the set of supernets for an
instance \(I\) of CRRB and an extension \(I'\) of \(I\) with the same
character\@. The same will be done for the corresponding supernets and
the corresponding nets contained in the supernets\@. Let \(I'\) be an
extension of an instance \(I=(k,p,\setofsupernets{N})\) for CRRB\@. A
routing for \(I'\) is an \emph{extension} of a routing for \(I\) if
both routings are identical on all columns up to column \(p-1\)\@.
%
\begin{alabsubtext}{Example}{2}{}
\exampfontshape
%
Consider the instance \(I=(4,7,\setofsupernets{N})\) where
\(\setofsupernets{N}\) is as in Example~1\@. Let
\(I'=(4,10,\setofsupernets{N})\), where
\(\setofsupernets{N}=\{N_{1},N_{2},N_{3},N_{4}\}\) of \(I'\)
contains the supernets \(N_{1}=\{(1,10)_{t}\}\),
\(N_{2}=\{(1,3)_{b},(6,8)_{t},(9,10)_{b}\}\),
\(N_{3}=\{(2,4)_{t},(5,8)_{b},(9,10)_{t}\}\), and
\(N_{4}=\{(3,10)_{t}\}\)\@. Then, \(I'\) is an extension of \(I\)\@. A
routing for \(I'\) that is an extension of the routing for \(I\)
from the right part of Figure~2 is given in Figure~3\@.
%
\end{alabsubtext}
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(3062,1995)(0,-10)
\put(2835,972){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\path(495,1692)(2745,1692)(2745,567)(495,567)
\dashline{60.000}(495,1467)(1170,1467)
\dashline{60.000}(495,1242)(945,1242)
\dashline{60.000}(1395,1242)(1845,1242)
\dashline{50.000}(2295,1242)(2520,1242)
\dashline{50.000}(495,1017)(720,1017)
\dashline{50.000}(495,792)(720,792)
\dashline{60.000}(1170,792)(1620,792)
\dashline{50.000}(2295,792)(2520,792)
\dashline{60.000}(2520,1242)(2520,792)
\dashline{60.000}(2295,1242)(2295,792)
\dashline{60.000}(2070,1692)(2070,567)
\dashline{60.000}(1845,1242)(1845,567)
\dashline{60.000}(1620,1692)(1620,792)
\dashline{60.000}(1395,1242)(1395,567)
\dashline{60.000}(1170,1467)(1170,792)
\dashline{60.000}(945,1242)(945,567)
\dashline{50.000}(720,1017)(720,792)
\put(2835,747){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(2835,1197){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(2835,1422){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(630,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(1080,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(2205,342){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(2430,342){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(2430,1872){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(2205,1872){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(1755,1872){\makebox(0,0)[lb]{\smash{\(N_{2}\)}}}
\put(1305,1872){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(1080,1872){\makebox(0,0)[lb]{\smash{\(N_{4}\)}}}
\put(855,1872){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\put(630,1872){\makebox(0,0)[lb]{\smash{\(N_{1}\)}}}
\put(0,27){\makebox(0,0)[lb]{\smash{column}}}
\put(675,27){\makebox(0,0)[lb]{\smash{\(1\)}}}
\put(900,27){\makebox(0,0)[lb]{\smash{\(2\)}}}
\put(1080,27){\makebox(0,0)[lb]{\smash{\(\dots\)}}}
\put(2025,27){\makebox(0,0)[lb]{\smash{\(7\)}}}
\put(2250,27){\makebox(0,0)[lb]{\smash{\(8\)}}}
\put(2475,27){\makebox(0,0)[lb]{\smash{\(9\)}}}
\put(2655,27){\makebox(0,0)[lb]{\smash{\(10\)}}}
\put(1530,342){\makebox(0,0)[lb]{\smash{\(N_{3}\)}}}
\thicklines
\path(720,1692)(720,1017)(2745,1017)
\path(945,1692)(945,1242)(1395,1242)(1395,1692)
\path(1170,1692)(1170,1467)(2745,1467)
\path(1845,1692)(1845,1242)(2295,1242)(2295,1692)
\path(2520,1692)(2520,1242)(2745,1242)
\path(720,567)(720,792)(1170,792)(1170,567)
\path(2520,567)(2520,792)(2745,792)
\path(1620,567)(1620,792)(2295,792)(2295,567)
\end{picture}
}
\end{center}
%
}}
\afigcap{3}{A routing for extension \protect\(I'\protect\)}
\end{figure*}
%
\apar{2-9}
An extension \(I'=(k,q,\setofsupernets{N})\) of an instance
\(I=(k,p,\setofsupernets{N})\) is \(\setofsupernets{M}\)-\emph{safe}
for \(I\), \(\setofsupernets{M}\subset\setofsupernets{N}\), if for
every routing for \(I'\) and each \(N\in\setofsupernets{M}\) the
supernet \(N\) terminates on track \(i\) in column \(q\) if and only if \(N\) is
on track \(i\) in column \(p\)\@.
%
\begin{alabsubtext}{Lemma}{1}{}
Let \(I=(k,p,\setofsupernets{N})\) be an instance of CRRB where all
\(k\) supernets in \(\setofsupernets{N}\) terminate with a top net
on the right boundary\@. Then, for each two different nets
\(N,N'\in\setofsupernets{N}\), there is an extension
\(I'=(k,p+5,\setofsupernets{N})\) of \(I\) such that:
%
\begin{enumerate}
%
\item[1.] the extension \(I'\) is \(\setofsupernets{N}\)-safe for \(I\),
%
\item[2.] all nets in \(I'\) terminate with a top net on the right boundary
in column \(p+5\), and
%
\item[3.] an assignment function
\(f\oftype\funcspace{\setofsupernets{N}}{[1:k]}\) is feasible
for the set N of supernets of I', if and only if f is feasible for the set N of
supernets of I and \(f(N)>f(N')\)\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{1}{}
\prooffontshape
%
\apar{Prove Lemma 1-1}
Let \(\setofsupernets{N}\) of \(I'\) be such that each net of the form
\((a,p)_t\) that is contained in any of the supernets in
\(\setofsupernets{N}-\{N,N'\}\) of \(I\) is replaced with a net
\((a,p+5)_{t}\)\@. Let supernets \(N\) and \(N'\) in
\(\setofsupernets{N}\) of \(I'\) be as in Figure~4\@. By construction,
condition~2 holds\@. To show conditions~1 and~3, assume that we have a
feasible assignment function \(f'\) for \(\setofsupernets{N}\) of
\(I'\), together with a corresponding routing for \(I'\)\@. Let \(f\) be
the assignment function where \(f(N'')\) is the number of the track
that is occupied by supernet \(N''\) in column \(p\), for each
\(N''\in\setofsupernets{N}\)\@. Clearly, \(f\) is feasible for
\(\setofsupernets{N}\) of \(I\)\@. Supernet \(N\) terminates with a top
net in column \(p+1\), leaving track \(f(N)\) free\@. Since track
\(f(N)\) is the only free track between columns \(p+1\) and \(p+2\),
the supernet \(N\) must occupy track \(f(N)\) again in column \(p+2\)\@.
Supernet \(N'\) terminates in column \(p+2\) with a top net\@. This is
possible only if \(f(N)>f(N')\) holds\@. Since \(f(N')\) is the only
free track between columns \(p+2\) and \(p+3\), supernet \(N'\) must
occupy track \(f(N')\) again in column \(p+3\)\@. Supernet \(N\)
terminates with a bottom net in column \(p+3\), leaving track \(f(N)\)
free; it occupies track \(f(N)\) in column \(p+4\), again starting
with a top net\@. Clearly, no other supernet can change its track in
columns \(p+1\) to \(p+4\)\@. We have \(f(N'')=f'(N'')\) for each
supernet \(N''\in\setofsupernets{N}\)\@. Thus, \(f'(N)>f'(N')\), \(f'\)
is feasible for \(\cal N\) of \(I\), and condition~1 holds\@.
%
\apar{Prove Lemma 1-2}
On the other hand, if we have a feasible assignment function \(f\) for
\(\setofsupernets{N}\) of \(I\) with \(f(N)>f(N')\), then it is easy
to show that \(f\) is also a feasible assignment function for
\(\setofsupernets{N}\) of \(I'\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 1}}
\end{alabsubtext}
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(3207,1914)(0,-10)
\put(2205,1026){\makebox(0,0)[lb]{\smash{\(=\)}}}
\put(0,36){\makebox(0,0)[lb]{\smash{column}}}
\put(1080,36){\makebox(0,0)[lb]{\smash{\(\dots\)}}}
\put(675,36){\makebox(0,0)[lb]{\smash{\(p+1\)}}}
\put(1575,36){\makebox(0,0)[lb]{\smash{\(p+5\)}}}
\put(2952,1094){\makebox(0,0)[cc]{\smash{\(N\mathord{\rightarrow}N'\)}}}
\path(2520,1656)(2610,1656)
\path(2520,531)(2610,531)
\path(3295,396)(3295,1791)(2610,1791)
        (2610,396)(3295,396)
\dashline{50.000}(1040,1206)(1265,1206)
\dashline{50.000}(810,981)(1035,981)
\dashline{50.000}(1260,981)(1485,981)
\dashline{50.000}(1260,1206)(1260,981)
\dashline{50.000}(1035,1206)(1035,981)
\path(585,1656)(1710,1656)(1710,531)(585,531)
\dashline{60.000}(810,981)(810,531)
\dashline{60.000}(1485,981)(1485,531)
\thicklines
\path(585,981)(810,981)(810,1656)
\path(1035,531)(1035,981)(1260,981)(1260,531)
\path(1485,1656)(1485,981)(1710,981)
\path(1260,1656)(1260,1206)(1710,1206)
\path(585,1206)(1035,1206)(1035,1656)
\put(1440,1791){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(1215,1791){\makebox(0,0)[lb]{\smash{\(N'\)}}}
\put(765,1791){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(945,1791){\makebox(0,0)[lb]{\smash{\(N'\)}}}
\put(1845,1161){\makebox(0,0)[lb]{\smash{\(N'\)}}}
\put(1845,936){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(1215,261){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(990,261){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(360,936){\makebox(0,0)[lb]{\smash{\(N\)}}}
\put(360,1161){\makebox(0,0)[lb]{\smash{\(N'\)}}}
\end{picture}
}
\end{center}
%
}}
\afigcap{4}{The supernets \protect\(N\protect\) and \protect\(N'\protect\)}
\end{figure*}
%
\apar{2-10}
With the help of this tool (Lemma~1), every order on the right border
can be enforced\@.
%
\begin{alabsubtext}{Lemma}{2}{}
%
For each \(k\), there is an instance \(I=(k,p,\setofsupernets{N})\) of
CRRB such that:
%
\begin{itemize}
%
\item all \(k\) supernets in \(\setofsupernets{N}\) terminate with a
top net on the right boundary, and
%
\item the only feasible assignment function is defined
by \(f(N_{i})=i\), i.e., in every routing for \(I\), supernet \(N_{i}\) must
terminate on track \(i\) on the right boundary\@.
%
\end{itemize}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2}{}
\prooffontshape
%
First, define an instance \(I=(k,k+1,\setofsupernets{N})\) of CRRB
where \(N_{i}=\{(i,k+1)_{t}\}\)\@. Obviously, for any assignment
function \(f\oftype\funcspace{\setofsupernets{N}}{{[1:k]}}\) we can find
a routing for \(I\)\@. By repeatedly using Lemma~1 we can extend \(I\)
to an instance \(I'\) such that there exists a routing for \(I'\) if
and only if for all \(i\in[1:k]\) supernet \(N_{i}\) terminates with a
top net that has a terminal on track \(i\) of the right boundary\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 2}}
\end{alabsubtext}
%
\asection{3}{The Main Theorems}
%
\apar{3-1}
We begin with a result about the complexity of CRRB\@. This result is
then used to show our main theorems about the complexity of Manhattan
channel routing with single-sided nets\@.
%
\begin{alabsubtext}{Theorem}{1}{}
%
CRRB is \(\complexityclass{NP}\)-complete even if the bottom nets
have density one and doglegs are allowed\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
%
\apar{Prove Theorem 1-1}
Obviously, our problem is in \(\complexityclass{NP}\)\@. To prove the
completeness for \(\complexityclass{NP}\), we reduce the
\emph{exactly-one-in-three} 3SAT problem to our problem\@. Let a set
\(\setofsupernets{C}=\{C_{1},C_{2},\dots,C_{m}\}\) of clauses, each of
size 3 over a set \(\Sigma =\{v_{1},v_{2},\dots,v_{n}\}\) of
variables, be an instance of exactly-one-in-three 3SAT\@. Without loss of generality we
can assume that no clause contains a negated literal (this restriction
is known to be \(\complexityclass{NP}\)-complete \cite{cj96-06-03})\@.
Recall that the exactly-one-in-three 3SAT problem asks whether there
is a truth assignment of the variables in \(\Sigma\) such that each
clause in \(\setofsupernets{C}\) contains exactly one true literal\@.
%
\apar{Prove Theorem 1-2}
The idea of the proof is as follows\@. We begin by constructing an
instance of CRRB\@. We divide the tracks of the channel into five
consecutive groups \(G_{1},\dots,G_{5}\)\@. Tracks in \(G_{i}\) are
above the tracks in \(G_{i+1}\) for \(i\in[1:4]\)\@. For each clause
\(C_l=\{v_h,v_i,v_j\}\), we introduce three supernets \(V_{h}^{l}\),
\(V_{i}^{l}\), and \(V_{j}^{l}\) that must terminate on tracks in
group \(G_{2}\) on the right boundary in each routing\@. Furthermore,
for each variable \(v_{i}\) we introduce two supernets \(H_{i}\) and
\(L_{i}\) that must terminate on tracks in group \(G_{3}\) on the
right boundary in each routing\@. Then we extend our instance and
enforce that for each variable \(v_{i}\), either \(H_{i}\) changes to
a track in group \(G_{1}\) or \(L_{i}\) changes to a track in group
\(G_{5}\)\@. This will give us a truth assignment for the variables\@.
Furthermore, we force all supernets of the form \(V_{i}^{l}\) to
change to a track of group \(G_{4}\) if and only if for the corresponding
variable \(v_{i}\) the supernet \(L_{i}\) is on a track in group
\(G_{5}\)\@. In addition, we require that exactly one of the three
supernets \(V_{h}^{l}\), \(V_{i}^{l}\), and \(V_{j}^{l}\) for a clause
\(C_{l}\) will change to a track in group \(G_{4}\)\@. Thus, there will
be a routing if and only if there exists a truth assignment for the variables
satisfying \(\setofsupernets{C}\)\@.
%
\apar{Prove Theorem 1-3}
We formalize these ideas\@. Let \(k=8n+7m\) be the number of tracks\@. We
divide the channel into the five groups
\(G_{1}=\setof{\operatorname{track}i}{i\in[1:3n]}\),
\(G_{2}=\setof{\operatorname{track}i}{i\in [3n+1:3n+6m]}\),
\(G_{3}=\setof{\operatorname{track}i}{i\in [3n+6m+1:5n+6m]}\),
\(G_{4}=\setof{\operatorname{track}i}{i\in[5n+6m+1:5n+7m]}\), and
\(G_{5}=\setof{\operatorname{track}i}{i\in[5n+7m+1:8n+7m]}\)\@. Based on
Lemma~2, we construct an instance
\(I_{0}=(k,p_{0},\setofsupernets{N})\) of CRRB as follows:
%
\begin{enumerate}
%
\item[1.] For each variable \(v_{i}\), \(i\in[1:n]\), we have a set
\(\setofsupernets{V}_{i}\) consisting of 8 supernets
\[\setofsupernets{V}_{i}=
  \{A_{i},A_{i}',B_{i},B_{i}',B_{i}'',B_{i}''',H_{i},L_{i}\}\]
\sentence
%
\item[2.] For each clause \(C_{l}=\{v_{h},v_{i},v_{j}\}\), \(l\in[1:m]\),
we have a set \(\setofsupernets{C}_{l}\) of 7 supernets
  \[\setofsupernets{C}_{l}=
    \{V_{h}^{l},V_{i}^{l},V_{j}^{l},X_{l},X_{l}',X_{l}'',Y_{l}\}\]
\sentence
%
\end{enumerate}
%
\apar{Prove Theorem 1-4}
Now we set
\(\setofsupernets{N}=
  \unionofset{i\in[1:n]}{\setofsupernets{V}_{i}}\setunion
  \unionofset{l\in[1:m]}{\setofsupernets{C}_{l}}\)\@.
Further, \(I_{0}=(k,p,\setofsupernets{N})\) is constructed such that there
exists a routing for \(I_{0}\) if and only if the supernets in
\(\setofsupernets{N}\) terminate with a top net on the right boundary
in the following ways:
%
\begin{enumerate}
%
\item[3.] For each variable \(v_{i}\), \(i\in[1:n]\), the terminals on the
right boundary for the supernets are as follows:
%
\begin{enumerate}
%
\item[(a)] \(B_{i}\), \(B_{i}'\), \(A_{i}'\) are in this order on
neighboring tracks in \(G_{1}\) (more precisely, they are on tracks
\(3i-2\), \(3i-1\), and \(3i\))\@.
%
\item[(b)] \(L_{i}\), \(H_{i}\) are in this order on neighboring tracks in
\(G_{3}\) (more precisely, they are on tracks \(3n+6m+2i-1\) and
\(3n+6m+2i\))\@.
%
\item[(c)] \(A_{i}\), \(B_{i}''\), \(B_{i}'''\) are in this order on
neighboring tracks in \(G_{5}\) (more precisely, they are on tracks
\(5n+7m+3i-2\), \(5n+7m+3i-1\), and \(5n+7m+3i\))\@.
%
\end{enumerate}
%
\item[4.] For each clause \(C_{l}=\{v_{h},v_{i},v_{j}\}\),
\(l\in[1:m]\), \(h<i<j\), the terminals on the right boundary for
the supernets are as follows:
%
\begin{enumerate}
%
\item[(a)] \(X_{l}\), \(V_{h}^{l}\), \(V_{i}^{l}\), \(V_{j}^{l}\),
\(X_{l}'\), \(X_{l}''\) are in this order on neighboring tracks in
\(G_{2}\) (more precisely, they are on tracks \(3n+6l-5,\ldots ,3n+6l\))\@.
%
\item[(b)] \(Y_{l}\) is on a track in \(G_{4}\) (more precisely, it is on track
\(5n+6m+l\))\@.
%
\end{enumerate}
%
\end{enumerate}
%
\apar{Prove Theorem 1-5}
We now extend our instance \(I_{0}\) step by step, in such a manner
that we can fix a truth assignment for the variables in \(\Sigma\)\@.
One extension step is performed for each variable in \(V\)\@. Let
\(I_{i}=(k,p_{i},\setofsupernets{N})\) be the extended instance after
the \(i\)th extension step\@. The effect of the \(i\)th extension will
be that there is a routing for the extended instance \(I_{i}\) if and only if
either supernet \(H_{i}\) terminates on a track in \(G_{1}\) on the
right boundary, or \(L_{i}\) terminates on a track in \(G_{5}\) on the
right boundary\@. In the first case, variable \(v_{i}\) will be false;
in the other case, it will be true\@. The extension \(I_{i}\) is given
in Figures~5 and~6\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5844,4605)(0,-10)
\put(405,3177){\makebox(0,0)[lb]{\smash{\(A_{i}'\)}}}
\put(405,1602){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(405,1377){\makebox(0,0)[lb]{\smash{\(B_{i}''\)}}}
\put(405,1152){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(405,2277){\makebox(0,0)[lb]{\smash{\(H_{i}\)}}}
\put(405,2502){\makebox(0,0)[lb]{\smash{\(L_{i}\)}}}
\put(405,3402){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(405,3627){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(810,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(1260,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(1710,4257){\makebox(0,0)[lb]{\smash{\(B''_{i}\)}}}
\put(2610,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(2160,4257){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(1935,4482){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(1485,4482){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(1035,4482){\makebox(0,0)[lb]{\smash{\(B_{i}''\)}}}
\put(2385,432){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(1485,432){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(4185,4257){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(3735,4257){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(3262,2390){\makebox(0,0)[cc]{\smash{%
\(\setlength{\jot}{3ex}\begin{aligned}
  A_{i}' & \mathord{\rightarrow}A_{i} \\
  B_{i}' & \mathord{\rightarrow}B_{i} \\
  B_{i}'' & \mathord{\rightarrow}B_{i}' \\
  B_{i}''' & \mathord{\rightarrow}B_{i}''
\end{aligned}\)}}}
\put(4837,2390){\makebox(0,0)[cc]{\smash{\(L_{i}\rightarrow H_{i}\)}}}
\put(3780,117){\makebox(0,0)[lb]{\smash{\(q_{i}\)}}}
\put(5355,162){\makebox(0,0)[lb]{\smash{\(p_{i}\)}}}
\put(675,162){\makebox(0,0)[lb]{\smash{\(p_{i-1}+1\)}}}
\dashline{60.000}(1575,3627)(2250,3627)
\dashline{60.000}(900,3402)(2025,3402)
\dashline{50.000}(1575,3177)(1800,3177)
\dashline{60.000}(2700,1152)(2700,702)
\dashline{60.000}(2475,4077)(2475,1152)
\dashline{60.000}(2250,3627)(2250,702)
\dashline{60.000}(2025,3402)(2025,702)
\dashline{60.000}(1800,3177)(1800,702)
\dashline{60.000}(1575,3627)(1575,3177)
\dashline{50.000}(1575,1377)(1575,1152)
\dashline{60.000}(1125,1377)(1125,702)
\dashline{60.000}(900,3402)(900,702)
\dashline{60.000}(1350,1152)(1350,702)
\dashline{60.000}(1125,1377)(1575,1377)
\dashline{50.000}(1375,1152)(1575,1152)
\dashline{50.000}(2475,1152)(2700,1152)
\thicklines
\path(675,3402)(900,3402)(900,4077)
\path(675,3627)(1575,3627)(1575,4077)
\path(675,2502)(2880,2502)
\path(675,2277)(2880,2277)
\path(2250,4077)(2250,3627)(2880,3627)
\path(675,1377)(1125,1377)(1125,4077)
\path(675,1152)(1350,1152)(1350,4077)
\path(1575,702)(1575,1152)(2475,1152)(2475,702)
\path(2880,1152)(2700,1152)(2700,4077)
\thinlines
\path(675,4077)(2880,4077)
\path(675,702)(2880,702)
\thicklines
\path(675,3177)(1575,3177)(1575,1377)(2880,1377)
\path(2025,4077)(2025,3402)(2880,3402)
\path(1800,4077)(1800,3177)(2880,3177)
\path(675,1602)(2880,1602)
\thinlines
\dashline{60.000}(3825,3402)(3825,702)
\dashline{60.000}(4050,4077)(4050,702)
\dashline{60.000}(4275,2277)(4275,702)
\dashline{50.000}(3825,3402)(4050,3402)
\dashline{50.000}(4095,2277)(4320,2277)
\thicklines
\path(3645,4077)(4455,4077)
\path(3645,702)(4455,702)
\path(5220,4077)(5400,4077)(5400,702)(5220,702)
\path(5220,3402)(5400,3402)
\path(5220,3177)(5400,3177)
\path(5220,2502)(5400,2502)
\path(5220,2277)(5400,2277)
\path(5220,1602)(5400,1602)
\path(5220,1377)(5400,1377)
\path(5220,1152)(5400,1152)
\path(3645,3177)(4455,3177)
\path(3645,2502)(4455,2502)
\path(4275,4077)(4275,2277)(4455,2277)
\path(3645,1602)(4455,1602)
\path(3645,1377)(4455,1377)
\path(3645,1152)(4455,1152)
\path(3645,2277)(4050,2277)(4050,3402)(4455,3402)
\thinlines
\path(5220,522)(5220,4257)(4455,4257)
        (4455,522)(5220,522)
\path(3285,567)(3285,567)(3285,567)
        (3285,567)(3285,567)
\path(3645,522)(3645,4257)(2880,4257)
        (2880,522)(3645,522)
\thicklines
\path(5220,3627)(5400,3627)
\path(3645,3627)(4455,3627)
\path(3645,3402)(3825,3402)(3825,4077)
\put(5580,2457){\makebox(0,0)[lb]{\smash{\(s\)}}}
\put(5580,1557){\makebox(0,0)[lb]{\smash{\(t\)}}}
\put(5580,3582){\makebox(0,0)[lb]{\smash{\(r\)}}}
\put(5445,4257){\makebox(0,0)[lb]{\smash{track}}}
\put(0,117){\makebox(0,0)[lb]{\smash{column}}}
\end{picture}
}
\end{center}
%
}}
\afigcap{5}{Routing for extension \protect\(I_{i}\protect\):
  \protect\(v_{i}\protect\) \emph{false}}
\end{figure*}
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5844,4605)(0,-10)
\put(405,3177){\makebox(0,0)[lb]{\smash{\(A_{i}'\)}}}
\put(405,1602){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(405,1377){\makebox(0,0)[lb]{\smash{\(B_{i}''\)}}}
\put(405,1152){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(405,2277){\makebox(0,0)[lb]{\smash{\(H_{i}\)}}}
\put(405,2502){\makebox(0,0)[lb]{\smash{\(L_{i}\)}}}
\put(405,3402){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(405,3627){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(810,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(1260,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(1710,4257){\makebox(0,0)[lb]{\smash{\(B_{i}''\)}}}
\put(2610,4257){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(2160,4257){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(1935,4482){\makebox(0,0)[lb]{\smash{\(B_{i}'\)}}}
\put(1485,4482){\makebox(0,0)[lb]{\smash{\(B_{i}\)}}}
\put(1035,4482){\makebox(0,0)[lb]{\smash{\(B_{i}''\)}}}
\put(2385,432){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(1485,432){\makebox(0,0)[lb]{\smash{\(B_{i}'''\)}}}
\put(4185,4257){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(3735,4257){\makebox(0,0)[lb]{\smash{\(A_{i}\)}}}
\put(3262,2390){\makebox(0,0)[cc]{\smash{%
\(\setlength{\jot}{3ex}\begin{aligned}
  A_{i}' & \mathord{\rightarrow}A_{i} \\
  B_{i}' & \mathord{\rightarrow}B_{i} \\
  B_{i}'' & \mathord{\rightarrow}B_{i}' \\
  B_{i}''' & \mathord{\rightarrow}B_{i}''
\end{aligned}\)}}}
\put(4837,2390){\makebox(0,0)[cc]{\smash{\(L_{i}\rightarrow H_{i}\)}}}
\put(3780,117){\makebox(0,0)[lb]{\smash{\(q_{i}\)}}}
\put(5355,162){\makebox(0,0)[lb]{\smash{\(p_{i}\)}}}
\put(675,162){\makebox(0,0)[lb]{\smash{\(p_{i-1}+1\)}}}
\dashline{60.000}(1575,3627)(2250,3627)
\dashline{60.000}(900,3402)(2025,3402)
\dashline{50.000}(1575,3177)(1800,3177)
\dashline{60.000}(2700,1152)(2700,702)
\dashline{60.000}(2475,4077)(2475,1152)
\dashline{60.000}(2250,3627)(2250,702)
\dashline{60.000}(2025,3402)(2025,702)
\dashline{60.000}(1800,3177)(1800,702)
\dashline{60.000}(1575,3627)(1575,3177)
\dashline{50.000}(1575,1377)(1575,1152)
\dashline{60.000}(1125,1377)(1125,702)
\dashline{60.000}(900,3402)(900,702)
\dashline{60.000}(1350,1152)(1350,702)
\dashline{60.000}(1125,1377)(1575,1377)
\dashline{50.000}(1375,1152)(1575,1152)
\dashline{50.000}(2475,1152)(2700,1152)
\dashline{60.000}(3825,1602)(3825,702)
\dashline{60.000}(4050,1602)(4050,702)
\dashline{60.000}(4050,4077)(4050,2502)
\dashline{60.000}(4275,2502)(4275,702)
\path(3645,4077)(4455,4077)
\path(3645,702)(4455,702)
\path(5220,4077)(5400,4077)(5400,702)(5220,702)
\dashline{50.000}(4050,2502)(4275,2502)
\dashline{50.000}(3825,1602)(4050,1602)
\thicklines
\path(5220,3402)(5400,3402)
\path(5220,3177)(5400,3177)
\path(5220,2502)(5400,2502)
\path(5220,2277)(5400,2277)
\path(5220,1602)(5400,1602)
\path(5220,1377)(5400,1377)
\path(5220,1152)(5400,1152)
\path(3645,3177)(4455,3177)
\path(3645,1152)(4455,1152)
\path(675,3402)(900,3402)(900,4077)
\path(675,3627)(1575,3627)(1575,4077)
\path(675,2502)(2880,2502)
\path(675,2277)(2880,2277)
\path(2250,4077)(2250,3627)(2880,3627)
\path(675,1377)(1125,1377)(1125,4077)
\path(675,1152)(1350,1152)(1350,4077)
\path(1575,702)(1575,1152)(2475,1152)(2475,702)
\path(2880,1152)(2700,1152)(2700,4077)
\thinlines
\path(5220,522)(5220,4257)(4455,4257)
        (4455,522)(5220,522)
\path(3285,567)(3285,567)(3285,567)
        (3285,567)(3285,567)
\path(3645,522)(3645,4257)(2880,4257)
        (2880,522)(3645,522)
\path(675,4077)(2880,4077)
\path(675,702)(2880,702)
\thicklines
\path(3645,3402)(4455,3402)
\path(3645,1377)(4455,1377)
\path(3645,1602)(3825,1602)(3825,4077)
\path(3645,2277)(4455,2277)
\path(4275,4077)(4275,2502)(4455,2502)
\path(3645,2502)(4050,2502)(4050,1602)(4455,1602)
\path(675,3177)(1575,3177)(1575,1377)(2880,1377)
\path(2025,4077)(2025,3402)(2880,3402)
\path(1800,4077)(1800,3177)(2880,3177)
\path(675,1602)(2880,1602)
\path(3645,3627)(4455,3627)
\path(5220,3627)(5400,3627)
\put(5580,2457){\makebox(0,0)[lb]{\smash{\(s\)}}}
\put(5580,1557){\makebox(0,0)[lb]{\smash{\(t\)}}}
\put(5445,4257){\makebox(0,0)[lb]{\smash{track}}}
\put(0,117){\makebox(0,0)[lb]{\smash{column}}}
\put(5580,3582){\makebox(0,0)[lb]{\smash{\(r\)}}}
\end{picture}
}
\end{center}
%
}}
\afigcap{6}{Routing for extension \protect\(I_{i}\protect\):
  \protect\(v_{i}\protect\) \emph{true}}
\end{figure*}
%
\begin{alabsubtext}{Claim}{1}{}
For all \(i\in[1:n]\):
%
\begin{enumerate}
%
\item[1.] Extension \(I_{i}\) is
\((\setofsupernets{N}-\setofsupernets{V}_{i})\)-safe for
\(I_{i-1}\)\@.
%
\item[2.] All supernets of \(I_{i}\) terminate with a top net on the right
boundary\@.
%
\item[3.] In each routing for \(I_{i}\), either
%
\begin{enumerate}
%
\item[(a)] \(H_{i}\) terminates on a track in \(G_{1}\) and \(L_{i}\)
terminates on a track in \(G_{3}\) on the right boundary, or 
%
\item[(b)] \(H_{i}\) terminates on a track in \(G_{3}\) and \(L_{i}\)
terminates on a track in \(G_{5}\) on the right boundary\@.
%
\end{enumerate}
%
\item[4.] For both cases in condition~3, there exist such a routing\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Claim}{1}{}
\prooffontshape
%
\apar{Prove Claim 1-1}
By construction, condition~2 holds\@. We must show conditions 1, 3, and
4\@. We are given a routing for \(I_{i-1}\)\@. Let \(B_{i}\), \(L_{i}\),
and \(A_{i}\) terminate on tracks \(r\), \(s\), and \(t\),
respectively (see Figures~5 and~6)\@. We want to find all possible
extensions of this routing to a routing for \(I_{i}\)\@.
%
\apar{Prove Claim 1-2}
The supernets \(B_{i}'\), \(B_{i}''\), and \(B_{i}'''\) terminate in
columns \(p_{i-1}+1\) to \(p_{i-1}+3\)\@. There is only one possibility
to route in these three columns (see Figure~5)\@. Since we force
\(A_{i}'\rightarrow A_{i}\) behind column \(p_{i}+9\) and we have
\(A_{i}\rightarrow A_{i}'\) in column \(p_{i-1}+3\), it must be the
case that \(A_{i}\) and \(A_{i}'\) change the order of their tracks in
columns \(p_{i-1}+4\) to \(p_{i-1}+9\)\@. Obviously, this change is not
possible in columns \(p_{i-1}+8\) and \(p_{i-1}+9\) (in these columns,
\(B_{i}'''\) terminates with a bottom net and starts again with a top
net, and no other net can change its track)\@. In columns \(p_{i-1}+5\)
to \(p_{i-1}+7\), the supernets \(B_{i}''\), \(B_{i}'\), and \(B_{i}\)
start with top nets\@. Since we force \(B_{i}''\rightarrow B_{i}'\) and
\(B_{i}'\rightarrow B_{i}\) behind column \(p_{i-1}+9\), the supernet
\(B_{i}''\) has to start on the bottommost free track in column
\(p_{i-1}+5\), and \(B_{i}'\) has to start on the bottommost free
track in column \(p_{i-1}+6\)\@. No net other than \(B_{i}''\),
\(B_{i}'\), or \(B_{i}\) can change its track in columns \(p_{i-1}+5\)
to \(p_{i-1}+7\)\@. Hence, nets \(A_{i}'\) and \(A_{i}\) must change the
order of their tracks in column \(p_{i-1}+4\)\@.
%
\apar{Prove Claim 1-3}
Assume that \(A_{i}\) changes its track in column \(p_{i-1}+4\) in
such a way that \(A_{i}'\rightarrow A_{i}\) holds\@. See Figure 5 for
this case\@. The only possibility is that \(A_{i}\) changes to track
\(r+1\) in column \(p_{i-1}+4\)\@. Further, \(B_{i}'''\) starts on
track \(t+2\) of column \(p_{i-1}+5\)\@. \(B_{i}'''\) cannot start on
track \(t+1\), because we force \(B_{i}'''\rightarrow B_{i}''\) behind
column \(p_{i-1}+9\) and \(B_{i}'''\) cannot change its track in
columns \(p_{i-1}+5\) to \(p_{i-1}+9\)\@. No net other than \(B_{i}\),
\(A_{i}\), or \(B_{i}'''\) can change its track in column
\(p_{i-1}+4\)\@. Thus, there is only one possible routing in columns
\(p_{i-1}+5\) to \(p_{i-1}+9\) for the case that \(A_{i}\) changes its
track\@.
%
\apar{Prove Claim 1-4}
In column \(q_{i}-1\) we have \(H_{i}\rightarrow L_{i}\), and we force
\(L_{i}\rightarrow H_{i}\) behind column \(q_{i}+2\)\@. Hence, \(L_{i}\)
and \(H_{i}\) must change the order of their tracks in columns
\(q_{i}\) to \(q_{i}+2\)\@. \(A_{i}\) terminates in column \(q_{i}\) on
a track in \(G_{1}\) and starts again in column \(q_{i}+2\)\@. The only
possibility for \(L_{i}\) and \(H_{i}\) to change their tracks is that
\(H_{i}\) changes its track in column \(q_{i}+1\) to the free track in
\(G_{1}\) (see Figure~5)\@. No net other than \(H_{i}\) or \(A_{i}\) can
change its track in columns \(q_{i}\) to \(q_{i}+2\)\@.
%
\apar{Prove Claim 1-5}
In view of the above, there is only one possible routing for the case
that \(A_{i}\) changes its track (see Figure~5)\@. This routing is
\((\setofsupernets{N}-\setofsupernets{V}_{i})\)-safe for \(I_{i-1}\),
\(H_{i}\) terminates on a track in \(G_{1}\), and \(L_{i}\) terminates
on a track in \(G_{3}\) on the right boundary\@. Analogously, it can be
seen that there is only one routing for the case that \(A_{i}'\)
changes its track (see Figure~6)\@. This routing is
\((\setofsupernets{N}-\setofsupernets{V}_{i})\)-safe for \(I_{i-1}\),
\(H_{i}\) terminates on a track in \(G_{3}\), and \(L_{i}\) terminates
on a track in \(G_{5}\) on the right boundary\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Claim 1}}
\end{alabsubtext}
%
\apar{Prove Theorem 1-6}
Now, we extend our instance \(I_{n}\) step by step in such a way that
we can choose exactly one true variable in each clause\@. One extension
step is performed for each clause\@. Let
\(I_{n+l}=(k,p_{n+l},\setofsupernets{N})\) be the instance after the
\(l\)th extension step\@. The effect of the \(l\)th extension step will
be that there is a routing for \(I_{n+l}\) if and only if exactly one of the
three supernets \(V_{h}^{l}\), \(V_{i}^{l}\), or \(V_{j}^{l}\) changes
to a track in \(G_{4}\)\@. The extension \(I_{n+l}\) is given in
Figure~7\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0097ex}
%
\begin{center}
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(7673,4614)(0,-10)
\put(0,2646){\makebox(0,0)[lb]{\smash{\(X_{l}''\)}}}
\put(315,2871){\makebox(0,0)[lb]{\smash{\(X_{l}'\)}}}
\put(0,3096){\makebox(0,0)[lb]{\smash{\(V_{j}^{l}\)}}}
\put(0,3546){\makebox(0,0)[lb]{\smash{\(V_{h}^{l}\)}}}
\put(315,3816){\makebox(0,0)[lb]{\smash{\(X_{l}\)}}}
\put(315,3321){\makebox(0,0)[lb]{\smash{\(V_{i}^{l}\)}}}
\put(2520,2646){\makebox(0,0)[lb]{\smash{\(X_{l}''\)}}}
\put(2835,2871){\makebox(0,0)[lb]{\smash{\(X_{l}'\)}}}
\put(2520,3096){\makebox(0,0)[lb]{\smash{\(V_{j}^{l}\)}}}
\put(2520,3546){\makebox(0,0)[lb]{\smash{\(V_{h}^{l}\)}}}
\put(2835,3816){\makebox(0,0)[lb]{\smash{\(X_{l}\)}}}
\put(2835,3321){\makebox(0,0)[lb]{\smash{\(V_{i}^{l}\)}}}
\put(5040,2646){\makebox(0,0)[lb]{\smash{\(X_{l}''\)}}}
\put(5355,2871){\makebox(0,0)[lb]{\smash{\(X_{l}'\)}}}
\put(5040,3096){\makebox(0,0)[lb]{\smash{\(V_{j}^{l}\)}}}
\put(5040,3546){\makebox(0,0)[lb]{\smash{\(V_{h}^{l}\)}}}
\put(5355,3816){\makebox(0,0)[lb]{\smash{\(X_{l}\)}}}
\put(5355,3321){\makebox(0,0)[lb]{\smash{\(V_{i}^{l}\)}}}
\put(675,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(1125,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(3195,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(3645,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(5715,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(6165,4491){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\dashline{60.000}(3285,1386)(3285,936)
\dashline{60.000}(3510,1386)(3510,936)
\dashline{60.000}(3735,3336)(3735,936)
\path(3105,4311)(3915,4311)
\path(3105,936)(3915,936)
\path(4815,4311)(4995,4311)(4995,936)(4815,936)
\dashline{60.000}(3105,3636)(3915,3636)
\dashline{50.000}(3285,1386)(3510,1386)
\dashline{60.000}(3510,4311)(3510,3336)
\thicklines
\path(3105,3861)(3915,3861)
\path(3105,2961)(3915,2961)
\path(3105,3186)(3915,3186)
\path(3105,1386)(3285,1386)(3285,4311)
\path(3105,2736)(3915,2736)
\path(3105,3636)(3915,3636)
\path(3735,4311)(3735,3411)(3915,3411)
\path(3105,3411)(3510,3411)(3510,1386)(3915,1386)
\thinlines
\dashline{60.000}(3105,3411)(3915,3411)
\dashline{50.000}(765,1386)(990,1386)
\thicklines
\path(585,2736)(1395,2736)
\thinlines
\dashline{60.000}(585,3636)(1395,3636)
\dashline{60.000}(765,1386)(765,936)
\dashline{60.000}(990,1386)(990,936)
\dashline{60.000}(1215,4311)(1215,936)
\path(585,4311)(1395,4311)
\path(585,936)(1395,936)
\path(2295,4311)(2475,4311)(2475,936)(2295,936)
\dashline{60.000}(990,4311)(990,3096)
\thicklines
\path(585,3861)(1395,3861)
\path(585,2961)(1395,2961)
\path(585,1386)(765,1386)(765,4311)
\path(585,3636)(1395,3636)
\path(585,3411)(1395,3411)
\path(1215,4311)(1215,3186)(1395,3186)
\path(585,3186)(990,3186)(990,1386)(1395,1386)
\thinlines
\dashline{60.000}(585,3186)(1395,3186)
\thicklines
\path(2295,3636)(2475,3636)
\path(2295,3411)(2475,3411)
\path(2295,1386)(2475,1386)
\path(2295,3861)(2475,3861)
\path(2295,3186)(2475,3186)
\path(2295,2961)(2475,2961)
\path(2295,2736)(2475,2736)
\thinlines
\dashline{60.000}(5805,1386)(5805,936)
\dashline{60.000}(6030,1386)(6030,936)
\dashline{60.000}(6255,3636)(6255,936)
\path(5625,4311)(6435,4311)
\path(5625,936)(6435,936)
\path(7380,4311)(7605,4311)(7605,936)(7335,936)
\dashline{60.000}(5625,3636)(6435,3636)
\dashline{50.000}(5805,1386)(6030,1386)
\thicklines
\path(5625,3411)(6435,3411)
\thinlines
\dashline{60.000}(6030,4311)(6030,3636)
\thicklines
\path(5625,3861)(6435,3861)
\path(5625,2961)(6435,2961)
\path(5625,3186)(6435,3186)
\path(5625,1386)(5805,1386)(5805,4311)
\path(5625,3636)(6030,3636)(6030,1386)(6435,1386)
\path(6255,4311)(6255,3636)(6435,3636)
\path(5625,2736)(6435,2736)
\path(7335,3636)(7605,3636)
\path(7335,3411)(7605,3411)
\path(7335,1386)(7605,1386)
\path(7335,3861)(7605,3861)
\path(7335,3186)(7605,3186)
\path(7335,2961)(7605,2961)
\path(7335,2736)(7605,2736)
\path(4815,3636)(4995,3636)
\path(4815,3411)(4995,3411)
\path(4815,1386)(4995,1386)
\path(4815,3861)(4995,3861)
\path(4815,3186)(4995,3186)
\path(4815,2961)(4995,2961)
\path(4815,2736)(4995,2736)
\thinlines
\path(2295,756)(2295,4491)(1395,4491)
        (1395,756)(2295,756)
\path(4815,756)(4815,4491)(3915,4491)
        (3915,756)(4815,756)
\path(7335,756)(7335,4491)(6435,4491)
        (6435,756)(7335,756)
\put(6705,36){\makebox(0,0)[lb]{\smash{\(\figlabel{c}\)}}}
\put(4185,36){\makebox(0,0)[lb]{\smash{\(\figlabel{b}\)}}}
\put(1665,36){\makebox(0,0)[lb]{\smash{\(\figlabel{a}\)}}}
\put(1800,2624){\makebox(0,0)[cc]{\smash{%
\(\setlength{\jot}{3ex}\begin{aligned}
  X_{l}'' & \mathord{\rightarrow}Y_{l} \\
  X_{l}' & \mathord{\rightarrow}Y_{l} \\
  Y_{l} & \mathord{\rightarrow}X_{l} \\
  X_{l}'' & \mathord{\rightarrow}X_{l}'
\end{aligned}\)}}}
\put(4320,2624){\makebox(0,0)[cc]{\smash{%
\(\setlength{\jot}{3ex}\begin{aligned}
  X_{l}'' & \mathord{\rightarrow}Y_{l} \\
  X_{l}' & \mathord{\rightarrow}Y_{l} \\
  Y_{l} & \mathord{\rightarrow}X_{l} \\
  X_{l}'' & \mathord{\rightarrow}X_{l}'
\end{aligned}\)}}}
\put(6840,2624){\makebox(0,0)[cc]{\smash{%
\(\setlength{\jot}{3ex}\begin{aligned}
  X_{l}'' & \mathord{\rightarrow}Y_{l} \\
  X_{l}' & \mathord{\rightarrow}Y_{l} \\
  Y_{l} & \mathord{\rightarrow}X_{l} \\
  X_{l}'' & \mathord{\rightarrow}X_{l}'
\end{aligned}\)}}}
\put(495,306){\makebox(0,0)[lb]{\smash{\(p_{n+l-1}+1\)}}}
\put(2295,306){\makebox(0,0)[lb]{\smash{\(p_{n+l}\)}}}
\put(3015,306){\makebox(0,0)[lb]{\smash{\(p_{n+l-1}+1\)}}}
\put(4815,306){\makebox(0,0)[lb]{\smash{\(p_{n+l}\)}}}
\put(5535,306){\makebox(0,0)[lb]{\smash{\(p_{n+l-1}+1\)}}}
\put(7335,306){\makebox(0,0)[lb]{\smash{\(p_{n+l}\)}}}
\put(315,1341){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(2835,1341){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\put(5355,1341){\makebox(0,0)[lb]{\smash{\(Y_{l}\)}}}
\end{picture}
}
\end{center}
%
}}
\afigcap{7}{Three routings for extension \protect\(I_{n+1}\protect\)}
\end{figure*}
%
\begin{alabsubtext}{Claim}{2}{}
For each clause \(C_{l}=\{v_{h},v_{i},v_{j}\}\in\setofsupernets{C}\),
the following hold:
%
\begin{enumerate}
\item[1.] Extension \(I_{n+l}\) is
  \((\setofsupernets{N}-\setofsupernets{C}_{l})\)-safe for
  \(I_{n+l-1}\)\@.
\item[2.] \(k\) supernets of \(I_{n+l}\) terminate with a top net on the right
  boundary\@.
\item[3.] In each routing for \(I_{n+l}\), exactly one of the three supernets
  \(V_{h}^{l}\), \(V_{i}^{l}\), or \(V_{j}^{l}\) terminates on a track
  in \(G_{4}\), and the other two terminate on a track in \(G_{2}\) on
  the right boundary\@.
\item[4.] For all three cases in condition~3, there exists such a routing\@.
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Claim}{2}{}
\prooffontshape
%
This claim is easily verified using arguments similar to the
ones used in the proof of Claim~1\@. The three possible routings for
columns \(p_{n+l-1}+1\) to \(p_{n+l-1}+3\) are shown in Figure~7\@.
{\nopagebreakbeginpar\markendlst{Proof of Claim 2}}
\end{alabsubtext}
%
\apar{Prove Theorem 1-7}
To finish our construction for Theorem~1, we extend the instance
\(I_{n+m}\) to the instance \(I=(k,p,\setofsupernets{N})\) by using
the construction of Lemma~1 in such a way that:
%
\begin{itemize}
\item[5.] For all \(i\in[1:n]\) and each \(l\in[1:m]\) with \(v_{i}\in
  C_{l}\), we have \(V_{i}^{l}\rightarrow H_{i}\) and
  \(L_{i}\rightarrow V_{i}^{l}\)\@.
\end{itemize}
%
\apar{Prove Theorem 1-8}
Observe that the bottom nets in \(\setofsupernets{N}\) of \(I\) have
density one\@. It remains to show that there exists a routing for \(I\)
if and only if there is a \(\setofsupernets{C}\)-satisfying truth assignment for
the variables in \(\Sigma\) such that there is exactly one true
literal in each clause\@.
%
\apar{Prove Theorem 1-9}
Assume that there exists a routing for \(I=(k,p,\setofsupernets{N})\)\@.
Now, set \(v_{i}\) to \emph{true} if \(L_{i}\) terminates on a track
in \(G_{5}\) and \(H_{i}\) terminates on a track in \(G_{3}\) at the
right boundary\@. Otherwise, set \(v_{i}\) to \emph{false}\@. Claim~1 and
condition~5 imply that for each variable \(v_{i}\) that has the value
\emph{false}, all supernets of the form \(V_{i}^{l}\) with \(v_{i}\in
C_{l}\) terminate on a track in \(G_{2}\) on the right boundary\@.
Furthermore, for each true variable \(v_{i}\), all supernets of the
form \(V_{i}^{l}\) with \(v_{i}\in C_{l}\) terminate on a track in
\(G_{4}\) on the right boundary\@. Since by Claim~2 and our
construction for each clause \(C_{l}=\{v_{h},v_{i},v_{h}\}\) exactly
one of the supernets \(V_{h}^{l}\), \(V_{i}^{l}\), or \(V_{j}^{l}\)
can terminate on a track in \(G_{4}\) on the right boundary and the
other two supernets terminate on a track in \(G_{2}\), there must be
exactly one true variable in each clause\@. On the other hand, if we
have a truth assignment satisfying \(\setofsupernets{C}\), we can
easily find a routing for \(I\) using Claims~1 and~2\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{3-2}
\begin{alabsubtext}{Theorem}{2}{}
%
The general Manhattan channel-routing problem (where doglegs are
allowed) and the restricted Manhattan channel-routing problem (where
doglegs are not allowed) are both \(\complexityclass{NP}\)-complete
for \(2\)-terminal nets in all of the following cases:
%
\begin{enumerate}
%
\item[1.] All nets are single-sided nets and the bottom nets have density
one\@.
%
\item[2.] All nets are two-sided, with the left terminal on the bottom boundary
and the right terminal on the top boundary\@.
%
\item[3.] All nets are single-sided top nets or two-sided nets with the left
terminal on the bottom boundary and the right terminal on the top
boundary, and the two-sided nets have density one\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
%
\apar{Prove Theorem 2-1}
First, we show that general Manhattan channel routing is
\(\complexityclass{NP}\)-complete in Case~1\@. It is easy to reduce
CRRB with bottom nets of density one to our problem\@. Let
\(I'=(k,p,\setofsupernets{N})\) be an instance of CRRB\@. To construct
an instance \(I\) of our problem, replace each net of the form
\((a,p)_{t}\) of a supernet \(N_{i}\) with the net \((a,p+i)_{t}\)\@.
Then, let instance \(I\) be the union of all the nets of the supernets
in \(\setofsupernets{N}\)\@. Clearly, there is a routing for \(I\) if
and only if there is a routing for \(I'\)\@. Slight variations of the
proofs of Theorem~1 and Lemmas~1 and~2 show that the cases of CRRB
corresponding to Cases~2 and~3 of Theorem~2 are
\(\complexityclass{NP}\)-complete\@. Then, using the same reduction as
in Case~1 above, one obtains that general Manhattan channel routing is
\(\complexityclass{NP}\)-complete in Cases~2 and~3\@.
%
\apar{Prove Theorem 2-2}
To show the results for restricted Manhattan channel routing is much
easier\@. Simplifications of the proofs for the general Manhattan
channel-routing problem will do\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%
\asection{4}{Routing in Irregular Channels}
%
\apar{4-1}
In this section, we consider Manhattan channel routing for channels
that have an irregular bottom boundary\@. 
%
\begin{alabsubtext}{Definition}{2}{}
A channel boundary is called \emph{irregular} if it is
not a straight line\@. For a channel with an irregular bottom boundary,
let \(h_{\max}\) (\(h_{\min}\)) be the maximum (respectively minimum) number of
(partial) tracks in one column, and set \(\Delta =h_{\max}-h_{\min}\)\@.
\end{alabsubtext}
%
\begin{figure*}
\setlength{\unitlength}{0.0123ex}
%
\begin{center}
\fbox{
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(2049,1460)(0,-300)
\path(12,1137)(2037,1137)(2037,12)
        (1587,12)(1587,237)(1362,237)
        (1362,462)(912,462)(912,12)
        (462,12)(462,237)(12,237)
\dashline{60.000}(12,912)(2037,912)
\dashline{60.000}(12,687)(2037,687)
\dashline{60.000}(12,462)(912,462)
\dashline{60.000}(462,237)(912,237)
\dashline{60.000}(1362,462)(2037,462)
\dashline{60.000}(1587,237)(2037,237)
\dashline{60.000}(1812,1137)(1812,12)
\dashline{60.000}(1587,1137)(1587,282)
\dashline{60.000}(1362,1137)(1362,507)
\dashline{60.000}(687,1137)(687,12)
\dashline{60.000}(462,1137)(462,282)
\dashline{60.000}(1137,1137)(1137,507)
\dashline{60.000}(237,1137)(237,282)
\dashline{60.000}(912,1137)(912,507)
\put(1024,-100){\makebox(0,0)[ct]{\(h_{\max}=4\), \(h_{\min}=2\), \(\Delta=2\)}}
\end{picture}
}}
\end{center}
%
\afigcap{8}{A channel with an irregular bottom boundary}
\end{figure*}
%
\apar{4-2}
Theorem 3, stated below, shows that even very simple routing problems
are \(\complexityclass{NP}\)-complete in this model\@.
%
\begin{alabsubtext}{Theorem}{3}{}
%
General and restricted Manhattan channel routing are both
\(\complexityclass{NP}\)-complete for channels with irregular bottom
boundaries, even if \(\Delta=1\) and there are only \(2\)-terminal top nets\@.
%
\end{alabsubtext}
%
\apar{4-3}
We omit the somewhat technical proof\@. Its overall structure is
similar to that of Theorem~2: first, one shows that results analogous
to Lemmas~1 and~2 hold, then one uses them to prove the appropriate
analogue of Theorem~1\@.
%
\asection{5}{Conclusion}
%
\apar{5-1}
We have shown that Manhattan channel routing with only single-sided or
only two-sided \(2\)-terminal nets is
\(\complexityclass{NP}\)-complete even for very restricted sets of
instances, regardless of whether or not doglegs are allowed\@.
Moreover, a quite restricted case of Manhattan channel routing for a
channel with one irregular boundary has been shown to be
\(\complexityclass{NP}\)-complete\@. Consequently, deterministic
polynomial algorithms for all Manhattan channel-routing problems that
involve one of our \(\complexityclass{NP}\)-complete problems are
unlikely to exist\@. This emphasizes the importance of heuristic
methods and approximation algorithms\@.
%
\bibliographystyle{\the\rbibstyle}
\bibliography{cj96-06}
%
\end{articletext}
%
\end{document}