Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1996, Article 6 30 December 1996

ISSN 1073–0486. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html

• http://www.cs.uchicago.edu/publications/cjtcs/

• gopher.mit.edu

• gopher.cs.uchicago.edu

• anonymous ftp at mitpress.mit.edu

• anonymous ftp at cs.uchicago.edu Middendorf Manhattan Channel Routing (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}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; journals-rights@mit.edu.

The 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.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

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ó 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 †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

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

Manhattan Channel Routing is NP-Complete under Truly Restricted Settings

Martin Middendorf

30 December, 1996

Abstract

Settling an open problem that is over ten years old, we show that

Abstract-1

Manhattan channel routing—with doglegs allowed—is NP-complete when all nets have two terminals. This result fills the gap left by Szymanski [Szy85], who showed the NP-completeness for nets with four terminals. Answering a question posed by Schmalenbach [Sch90] and Greenberg, Jájá, and Krishnamurty [GJK92], we prove that the problem remains 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 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.

1 Introduction

The channel-routing problem is a basic problem in the layout design of VLSI

1-1

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

Middendorf Manhattan Channel Routing §1

1 subcase, and it does arise in applications), and whether the nets are singlesided (all terminals of a net lie on the same boundary). The status of these restricted problems is discussed below.

The routing subgraphs consist of horizontal and vertical segments. In

1-2

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).

It has been shown by LaPaugh [LaP80] that the decision version of the

1-3

dogleg-free Manhattan channel-routing problem is NP-complete, even when all nets have only two terminals. This result has been independently extended by Schmalenbach [Sch90] and Greenberg, Jájá, and Krishnamurty [GJK92]. They showed that restricted Manhattan channel routing with 2-terminal nets is NP-complete even when all nets are single-sided (i.e., both terminals lie on the same boundary).

The general Manhattan channel-routing problem—where doglegs are

1-4

allowed—seems harder to analyze, and its complexity is not well understood. Szymanski [Szy85] showed that the general Manhattan channelrouting problem is 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 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 [Sch90] and Greenberg, Jájá, and Krishnamurty [GJK92] stated that it is an interesting open problem whether Manhattan channel routing with 2-terminal, single-sided nets is also 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 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

2

Figure 1: A knock-knee

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 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.

All of our results also hold in the restricted Manhattan model. Thus, by

1-5

showing that Manhattan channel routing with single-sided, 2-terminal nets is NP-complete when doglegs are not allowed and the bottom nets have density one, we have extended the results of Schmalenbach and Greenberg, Jájá, and Krishnamurty.

Comparing Manhattan channel routing with knock-knee routing (where

1-6

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 [Len90]), our results show that Manhattan channel routing is the harder problem (unless P = NP). It is known that knock-knee routing is polynomial time solvable for 2-terminal nets [Fra82], [FWW93], whereas it is shown in this paper that general Manhattan channel routing is an NP-complete problem even for very restricted sets of 2-terminal nets. For nets with a larger number of terminals, knock-knee routing becomes NP-complete too. (It is NP-complete for 5terminal nets [Sar87]. The complexity for 3-terminal and 4-terminal nets is open.)

Our proof technique is also used to show that a quite restricted case of

1-7

routing in a channel where one boundary is slightly irregular is NP-complete. Note that this means that all practical cases which include our case are NPcomplete too.

In Section 2, we introduce some notation and another channel-routing

1-8

problem as a preparation of our main results. In Section 3, we show the NP-completeness of this problem. Minor modifications of this proof yield proofs of our results about the complexity of Manhattan channel routing.

3 In Section 4, we give our result for routing in a channel with an irregular boundary.

2 Preliminaries

A channel with a right boundary consists of a rectilinear grid that has bound-

2-1

aries 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 tracks. They are numbered 1, …, k from the topmost track to the bottommost track. The vertical grid lines (including the right boundary) are the columns. Columns are numbered from left to right, with the right boundary at column p.

A 2-terminal net consists of two terminals located at grid points on the

2-2

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) starts at a and terminates at b. A net is a top (respectively bottom) 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 single-sided if it is a top or bottom net.

A supernet N for a channel with the right boundary at column p is a

2-3

set of nets { (a_{i}, b_{i})_{x_{i}} | i ∈ [1 : r], x_{i} ∈ {t, b} } with a_{1} < b_{1} < a_{2} < b_{2} < ⋯ < a_{r} < b_{r} ≤ p. A supernet starts (respectively terminates) at a column if it contains a net that starts (respectively terminates) at this column. A supernet is single-sided if all of its nets are single-sided.

For a set of nets M, the local density at column q is the number of nets

2-4

in M of the form (a, b) with a ≤ q ≤ b. The density of M is the maximum of the local densities over all columns.

Let N be a set of single-sided supernets for a channel with k tracks

2-5

and a right boundary at column p. A routing for N is an arrangement of routing paths in the channel for all the nets contained in the supernets in N with respect to the Manhattan model. Let N′ ⊂ N be the set of those supernets in N containing a net with a terminal on the right boundary. An

4

N_{1} N_{2} N_{2} N_{3}  N_{2} N_{4} N_{3} N_{3}N_{4}N_{3} N_{2}  N_{1} N_{2} N_{2} N_{3} N_{3}N_{4}N_{3} N_{2} N_{3} N_{1} N_{2} N_{4} column 1 2 …  7  column 1 2 …  7 N_{1}

Figure 2: Two routings for supernets N_{1}, …, N_{4}

injective function f: N′ → [1 : k] is called an assignment function for N. An assignment function is feasible if there exists a routing for N such that for each supernet N ∈ N′, the terminal on the right boundary of N is placed on track T_{f(N)}.

Example 1 Consider the set 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 N are given in Figure 2.

Our problem can now be formulated as follows.

2-6

Definition 1 (Channel Routing with Right Boundary)

Instance: A triple I = (k, p, N) with integers k, p and a set N = {N_{1}, N_{2}, …, N_{k}} of k single-sided supernets for a channel with k tracks and a right boundary at column p.

Question: Is there a routing for I, i.e., does there exist a feasible assignment function for N in a channel with k tracks and right boundary at column p?

We abbreviate this problem as CRRB.

Let I = (k, p, N) be an instance of CRRB. An extension of I is an

2-7

instance I′ = (k, q, N′) with q > p and N′ = {N′_{1}, N′_{2}, …, N′_{k}} such that for all i ∈ [1 : k], the following hold:

5

N_{1} N_{2} N_{3} N_{4} N_{2} N_{2}  N_{3}N_{2} N_{3} N_{2} N_{2} N_{3} N_{4} N_{3} N_{1} column 1 2 …  7 8 9 10 N_{3}

Figure 3: A routing for extension I′

1. For all (a, b)_{x} with b < p, x ∈ {b, t}, we have (a, b)_{x} ∈ N_{i} if and only if (a, b)_{x} ∈ N′_{i}.

2. If N_{i} contains a net of the form (a, p)_{x}, x ∈ {b, t}, then N′_{i} contains a net of the form (a, p′)_{x} for a p′ with p < p′ ≤ q.

To simplify the notation, we will denote the set of supernets for an in-

2-8

stance 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, N) for CRRB. A routing for I′ is an extension of a routing for I if both routings are identical on all columns up to column p − 1.

Example 2 Consider the instance I = (4, 7, N) where N is as in Example 1. Let I′ = (4, 10, N), where 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.

An extension I′ = (k, q, N) of an instance I = (k, p, N) is M-safe for

2-9

I, M ⊂ N, if for every routing for I′ and each N ∈ M the supernet N terminates on track i in column q if and only if N is on track i in column p.

Lemma 1 Let I = (k, p, N) be an instance of CRRB where all k supernets in N terminate with a top net on the right boundary. Then, for each two

6 different nets N, N′ ∈ N, there is an extension I′ = (k, p + 5, N) of I such that:

1. the extension I′ is N -safe for I,

2. all nets in I′ terminate with a top net on the right boundary in column p + 5, and

3. an assignment function f: 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′).

Proof of Lemma 1 Let N of I′ be such that each net of the form (a, p)_{t}

Prove Lemma 1-1

that is contained in any of the supernets in N − {N, N′} of I is replaced with a net (a, p + 5)_{t}. Let supernets N and N′ in 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 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′′ ∈ N. Clearly, f is feasible for 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′′ ∈ N. Thus, f′(N) > f′(N′), f′ is feasible for N of I, and condition 1 holds.

On the other hand, if we have a feasible assignment function f for N

Prove Lemma 1-2

of I with f(N) > f(N′), then it is easy to show that f is also a feasible assignment function for N of I′.

Proof of Lemma 1 □

With the help of this tool (Lemma 1), every order on the right border

2-10

can be enforced.

7

= column  … p + 1  p + 5  N→N′ N N ′ N N ′  N′ N N N N N′

Figure 4: The supernets N and N′

Lemma 2 For each k, there is an instance I = (k, p, N) of CRRB such that:

• all k supernets in N terminate with a top net on the right boundary, and

• 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.

Proof of Lemma 2 First, define an instance I = (k, k + 1, N) of CRRB where N_{i} = {(i, k + 1)_{t}}. Obviously, for any assignment function f: 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 ∈ [1 : k] supernet N_{i} terminates with a top net that has a terminal on track i of the right boundary.

Proof of Lemma 2 □

3 The Main Theorems

We begin with a result about the complexity of CRRB. This result is then

3-1

used to show our main theorems about the complexity of Manhattan channel routing with single-sided nets.

Theorem 1 CRRB is NP-complete even if the bottom nets have density one and doglegs are allowed.

8 Proof of Theorem 1 Obviously, our problem is in NP. To prove the com-

Prove Theorem 1-1

pleteness for NP, we reduce the exactly-one-in-three 3SAT problem to our problem. Let a set C = {C_{1}, C_{2}, …, C_{m}} of clauses, each of size 3 over a set Σ = {v_{1}, v_{2}, …, 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 NP-complete [GJ79]). Recall that the exactly-one-in-three 3SAT problem asks whether there is a truth assignment of the variables in Σ such that each clause in C contains exactly one true literal.

The idea of the proof is as follows. We begin by constructing an instance

Prove Theorem 1-2

of CRRB. We divide the tracks of the channel into five consecutive groups G_{1}, …, G_{5}. Tracks in G_{i} are above the tracks in G_{i+1} for i ∈ [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 C.

We formalize these ideas. Let k = 8n + 7m be the number of tracks.

Prove Theorem 1-3

We divide the channel into the five groups G_{1} = { track i | i ∈ [1 : 3n] }, G_{2} = { track i | i ∈ [3n + 1 : 3n + 6m] }, G_{3} = { track i | i ∈ [3n + 6m + 1 : 5n + 6m] }, G_{4} = { track i | i ∈ [5n + 6m + 1 : 5n + 7m] }, and G_{5} = { track i | i ∈ [5n + 7m + 1 : 8n + 7m] }. Based on Lemma 2, we construct an instance I_{0} = (k, p_{0}, N) of CRRB as follows:

1. For each variable v_{i}, i ∈ [1 : n], we have a set V_{i} consisting of 8 supernets

V_{i} = {A_{i}, A′_{i}, B_{i}, B′_{i}, B′′_{i}, B′′′_{i}, H_{i}, L_{i}}

2. For each clause C_{l} = {v_{h}, v_{i}, v_{j}}, l ∈ [1 : m], we have a set C_{l} of 7

supernets

C_{l} = {V_{h}^{l}, V_{i}^{l}, V_{j}^{l}, X_{l}, X′_{l}, X′′_{l}, Y_{l}}

9 Prove Theorem 1-4 Now we set N = ⋃_{i∈[1:n]} V_{i} ∪ ⋃_{l∈[1:m]} C_{l}. Further, I_{0} = (k, p, N) is con-

structed such that there exists a routing for I_{0} if and only if the supernets in N terminate with a top net on the right boundary in the following ways:

3. For each variable v_{i}, i ∈ [1 : n], the terminals on the right boundary for the supernets are as follows:

(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).

(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).

(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).

4. For each clause C_{l} = {v_{h}, v_{i}, v_{j}}, l ∈ [1 : m], h < i < j, the terminals on the right boundary for the supernets are as follows:

(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, …, 3n + 6l).

(b) Y_{l} is on a track in G_{4} (more precisely, it is on track 5n + 6m + l).

We now extend our instance I_{0} step by step, in such a manner that

Prove Theorem 1-5

we can fix a truth assignment for the variables in Σ. One extension step is performed for each variable in V. Let I_{i} = (k, p_{i}, N) be the extended instance after the ith extension step. The effect of the ith 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.

Claim 1 For all i ∈ [1 : n]:

1. Extension I_{i} is (N − V_{i})-safe for I_{i−1}.

2. All supernets of I_{i} terminate with a top net on the right boundary.

3. In each routing for I_{i}, either

10 A′_{i}

A_{i} B′′_{i} B′′′_{i} H_{i} L_{i} B′_{i} B_{i}

B′_{i} B′′′_{i} B′′_{i} B′′′_{i} B_{i}

B′′_{i} B_{i} B′_{i}

B′′′_{i} B′′′_{i}

A_{i} A_{i}

\begin{aligned}A′_{i} & →A_{i} \\ B′_{i} & →B_{i} \\ B′′_{i} & →B′_{i} \\ B′′′_{i} & →B′′_{i} \end{aligned}

L_{i} → H_{i}

q_{i} p_{i−1} + 1 p_{i}

s t r

track

column Figure 5: Routing for extension I_{i}: v_{i} false A′_{i}

A_{i} B′′_{i} B′′′_{i} H_{i} L_{i} B′_{i} B_{i}

B′_{i} B′′′_{i} B′′_{i} B′′′_{i} B_{i}

B′′_{i} B_{i} B′_{i}

B′′′_{i} B′′′_{i}

A_{i} A_{i}

\begin{aligned}A′_{i} & →A_{i} \\ B′_{i} & →B_{i} \\ B′′_{i} & →B′_{i} \\ B′′′_{i} & →B′′_{i} \end{aligned}

L_{i} → H_{i}

q_{i} p_{i−1} + 1 p_{i}

s t

track

column

r

Figure 6: Routing for extension I_{i}: v_{i} true (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

(b) H_{i} terminates on a track in G_{3} and L_{i} terminates on a track in G_{5} on the right boundary.

4. For both cases in condition 3, there exist such a routing.

Proof of Claim 1 By construction, condition 2 holds. We must show con-

Prove Claim 1-1

ditions 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}.

The supernets B′_{i}, B′′_{i}, and B′′′_{i} terminate in columns p_{i−1} + 1 to p_{i−1} + 3.

Prove Claim 1-2

There is only one possibility to route in these three columns (see Figure 5). Since we force A′_{i} → A_{i} behind column p_{i} +9 and we have A_{i} → 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} → B′_{i} and B′_{i} → 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.

Assume that A_{i} changes its track in column p_{i−1} + 4 in such a way that

Prove Claim 1-3

A′_{i} → 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} → 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.

In column q_{i} − 1 we have H_{i} → L_{i}, and we force L_{i} → H_{i} behind column

Prove Claim 1-4

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

13 Figure 5). No net other than H_{i} or A_{i} can change its track in columns q_{i} to q_{i} + 2.

In view of the above, there is only one possible routing for the case that

Prove Claim 1-5

A_{i} changes its track (see Figure 5). This routing is (N − 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 (N − 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.

Proof of Claim 1 □

Now, we extend our instance I_{n} step by step in such a way that we

Prove Theorem 1-6

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}, N) be the instance after the lth extension step. The effect of the lth 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.

Claim 2 For each clause C_{l} = {v_{h}, v_{i}, v_{j}} ∈ C, the following hold:

1. Extension I_{n+l} is (N − C_{l})-safe for I_{n+l−1}.

2. k supernets of I_{n+l} terminate with a top net on the right boundary.

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.

4. For all three cases in condition 3, there exists such a routing.

Proof of Claim 2 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.

Proof of Claim 2 □

To finish our construction for Theorem 1, we extend the instance I_{n+m}

Prove Theorem 1-7

to the instance I = (k, p, N) by using the construction of Lemma 1 in such a way that:

14 Middendorf Manhattan Channel Routing §3

X′′_{l}X′_{l} V_{j}^{l} V_{h}^{l} X_{l} V_{i}^{l}  X′′_{l}X′_{l} V_{j}^{l} V_{h}^{l} X_{l} V_{i}^{l}  X′′_{l}X′_{l} V_{j}^{l} V_{h}^{l} X_{l} V_{i}^{l} Y_{l} Y_{l}  Y_{l} Y_{l}  Y_{l} Y_{l} (c) (b) (a) \begin{aligned}X′′_{l} & →Y_{l} \\ X′_{l} & →Y_{l} \\ Y_{l} & →X_{l} \\ X′′_{l} & →X′_{l} \end{aligned}  \begin{aligned}X′′_{l} & →Y_{l} \\ X′_{l} & →Y_{l} \\ Y_{l} & →X_{l} \\ X′′_{l} & →X′_{l} \end{aligned}  \begin{aligned}X′′_{l} & →Y_{l} \\ X′_{l} & →Y_{l} \\ Y_{l} & →X_{l} \\ X′′_{l} & →X′_{l} \end{aligned} p_{n+l−1} + 1  p_{n+l} p_{n+l−1} + 1  p_{n+l} p_{n+l−1} + 1  p_{n+l} Y_{l}  Y_{l}  Y_{l}

Figure 7: Three routings for extension I_{n+1} 15

Chicago Journal of Theoretical Computer Science 1996-6 5. For all i ∈ [1 : n] and each l ∈ [1 : m] with v_{i} ∈ C_{l}, we have V_{i}^{l} → H_{i}

and L_{i} → V_{i}^{l}.

Observe that the bottom nets in N of I have density one. It remains to

Prove Theorem 1-8

show that there exists a routing for I if and only if there is a C-satisfying truth assignment for the variables in Σ such that there is exactly one true literal in each clause.

Assume that there exists a routing for I = (k, p, N). Now, set v_{i} to true if

Prove Theorem 1-9

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 false. Claim 1 and condition 5 imply that for each variable v_{i} that has the value false, all supernets of the form V_{i}^{l} with v_{i} ∈ 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} ∈ 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 C, we can easily find a routing for I using Claims 1 and 2.

Proof of Theorem 1 □

3-2

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 NP-complete for 2-terminal nets in all of the following cases:

1. All nets are single-sided nets and the bottom nets have density one.

2. All nets are two-sided, with the left terminal on the bottom boundary and the right terminal on the top boundary.

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.

Proof of Theorem 2 First, we show that general Manhattan channel rout-

Prove Theorem 2-1

ing is NP-complete in Case 1. It is easy to reduce CRRB with bottom nets of 16

h_{max} = 4, h_{min} = 2, Δ = 2

Figure 8: A channel with an irregular bottom boundary

density one to our problem. Let I′ = (k, p, 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 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 NP-complete. Then, using the same reduction as in Case 1 above, one obtains that general Manhattan channel routing is NP-complete in Cases 2 and 3.

To show the results for restricted Manhattan channel routing is much eas-

Prove Theorem 2-2

ier. Simplifications of the proofs for the general Manhattan channel-routing problem will do.

Proof of Theorem 2 □

4 Routing in Irregular Channels

In this section, we consider Manhattan channel routing for channels that

4-1

have an irregular bottom boundary.

Definition 2 A channel boundary is called 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 Δ = h_{max} − h_{min}.

Theorem 3, stated below, shows that even very simple routing problems

4-2

are NP-complete in this model.

17 Theorem 3 General and restricted Manhattan channel routing are both NPcomplete for channels with irregular bottom boundaries, even if Δ = 1 and there are only 2-terminal top nets.

We omit the somewhat technical proof. Its overall structure is similar to

4-3

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.

5 Conclusion

We have shown that Manhattan channel routing with only single-sided or

5-1

only two-sided 2-terminal nets is 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 NP-complete. Consequently, deterministic polynomial algorithms for all Manhattan channel-routing problems that involve one of our NP-complete problems are unlikely to exist. This emphasizes the importance of heuristic methods and approximation algorithms.

References

[Fra82] A. Frank. Disjoint paths in a rectilinear grid. Combinatorica, 2(4):361–371, 1982.

[FWW93] M. Formann, D. Wagner, and F. Wagner. Routing through a dense channel with minimum total wire length. Journal of Algorithms, 15(2):267–283, 1993.

[GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman, San Francisco, 1979.

[GJK92] R. Greenberg, J. Jájá, and S. Krishnamurty. On the difficulty of Manhattan channel routing. Information Processing Letters, 44(5):281–284, 1992.

[LaP80] A. S. LaPaugh. Algorithms for integrated circuit layout: an analytic approach. PhD thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, 1980.

18 Middendorf Manhattan Channel Routing

[Len90] T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Teubner, Stuttgart, 1990. Also published by Wiley in Chichester UK.

[Sar87] M. Sarrafzadeh. Channel-routing problem in the knock-knee mode is NP-complete. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 6(4):503–506, 1987.

[Sch90] C. Schmalenbach. Das Channel-Routing-Problem. Master’s thesis, Department of Mathematics, Technical University of Berlin, 1990. German.

[Szy85] T. G. Szymanski. Dogleg channel routing is NP-complete. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 4(1):31–41, 1985.

19