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