数理解析研究所講究録
第 1799 巻 2012 年 145-152145

グラフの正方格子上への単位長配置について
高田 健司 *1

天野一幸

はじめに
グラフ $G$ の各頂点を格子上に配置し (埋め込み),$\dagger$入 $;J$

グラフ $G$ .

問題$G$の単位長配置 $f$ を求めよ．の隣接する任意の 2 頂点について，2 頂点の格子上 配置 $fi$ が配置ゐの平行移動・画転・対称で表せるでの距離が 1 となる配置を単位長配置と呼ぶ．単位 とき，ゐとんを同じ配置とみなし，これらを同一解長配置は VLSI のレイアウトなどに応用を持ち，その として扱う．また，配置後のグラフはラベルなしグ$G$

判定問題は入力を木に限定しても NP 完全であることが証明されている [1]. 本稿では単位長配置の別解問題 (ASP) の計算複雑性をテーマとし，l-in-3 SATからの多項式時間 ASP 還元を示すことにより，木の単位長配置の ASP 完全性を証明する．

ラフとして扱い，同一の親を持つ葉の座標を入れ換えたものなどを同じ配置として扱う．

2.2

ASPASP(Another Solution Problem) とはある問題のインスタンス $I$ とその解

2

定義

き，の$I$$f\ddagger$

2.1

単位長配置

$s$

$s$

$\Pi$が 1 つ与えられたと以外の解を求める問題である．関数問題とそのインスタンス , 関数問題
$I$$\Pi’$について以下の (1),(2) が成り立つとき，垣から垣’ へ多項式時間

グラフ $G$ の頂点から整数値の二次元座標 $(x, y)$ への単射 $f(f:V(G)arrow Z^{2})$ を，グラフの正方格子へASP 還元可能という [3].

$uv\in E(G)$ に，距離関数 $d$ による以下のコストを与える．

兇糧縦衄任 ら’ の判定版への多項式時間還元(1)$f(u)=(i,j),$ $f(v)=(i’,j’)$ であるの配置と呼ぶ．

$\varphi_{D}$(2)$I$が存在する．の解集合から$\varphi_{D}(x)$計算可能な全単尉$d(f(8t),f(v))=|i-i’|+|j-j’|$$\varphi_{S}$の解集合への多項式時間が存在する．

クラス FNP(NP の関数版) の問題垣が，クラス FNP全ての辺のコストが 1( 上の単位距離) である単位長配置と呼ぶ (図 1).
$Z^{2}$を$f$の任意の問題垣’ から多項式時間 ASP 還元可能であるとき，問題 兇 ASP 完全と呼ぶ [3]. ASP 完全に属する問題垣から，FNP に属する問題 へ多項式時間 ASP 還元可能であるとき，間題 II’ の ASP 完全性が証明できる．ASP 完全である問題垣の性質の 1 つとして， のインスタンス とその解が 個$(k\geq 0)$ 与えられたとき， が与えられた個以外の解を持つかの判定が NP 完全であることが知られて$\Pi’$$f$$\infty$$I$$\Pi$.’$|$$|$$|$$|$.

$I$

$k$

$k$

いる．

図 1: 単位長配置の例

単位長配置の関数問題を次のように定義する．

3

群馬大学大学院工学研究科情報工学専攻
第 1 著者に同じ

本節で，木の単位長配置の関数問題の ASP 完全性を証明する．上記問題が FNP に属することは明らか$*$$\dagger$

木に対する ASP 完全性

146
まず，水平に L4n 3(頂点を とし，以後水平軸が正しいかのチェックが頂点数の多項式時間内で可 と記述) を配置し，頂点 $u_{4k+1}’,u_{4k+1}’’(1\leq k\leq n)$ をであり (解として各頂点の座標が与えられたとき，解能 , l-in-3 SAT からの多項式時間 ASP 還元を示す$u_{k}$$+$を追加する．水平軸にことによって ASP 完全性の証明を行う．l-in-3 SAT よって二分割された平面の上側を上部．下側を下部とは与えられた $3CNF$ 式 に対して，各節が真の値 とする．頂点 $u_{4k-1}(1\leq k\leq n+1)$ の 2 つ上の座標，のリテラルを丁度 1 つ持つ割当てが存在するかどう 2 つ下の座標を配置点と呼ぶ．配置点は上部下部にかを判定する問題である．この問題の関数版が ASP それぞれ $n+1$ 箇所ある．ただし上部右端の配置点完全であることは Yato, Seta によって証明されてい は，他の頂点によって使用されているものとする (図る [3]. これ以降，充足という言葉を l-in-3 SAT の 3 .
条件での充足” という意味で使う．
OO
はじめに，小節 31 で還元後のグラフの大多数の部
上部ロ
シシシ, 1I
11rtl– $0-LO$ – K-O 屋
分を構成するスパイングラフについて説明する．小節$)$基点とした垂直の $2n$ 個の$L_{2}$$\phi$

$)$

ロ

ロ

$|$

$O-O\sim O|$$\sigma_{-}^{1}\infty o$$0$$\mathfrak{o}$

$r$

$r$

’

$r\backslash$$r\backslash$$>$$\iota d$

32 では， の任意の節 に対応する，グラフの構造を変の構成を述べる．小節 33 にて，各$\phi$$C_{j}$$G_{C_{\dot{f}}}$$G_{C_{j}}$更接続し，任意の式$\phi$に対応するグラフ$G_{\phi}$$u_{\theta}$. .
.

$\iota 4$$|$$\ovalbox{\tt\small REJECT}$$\iota 4$$\iota d|$$|$$\frac{\text{◎◎}}{}-\cdot----\cdot\cdot$◎$– \frac{\text{〉}(}{}c_{h}$11 11111111111111111

OOOO$r\backslash$

への$0OO$$|$OOO. OOO. OO$|$$r\backslash$$|$$r\backslash$$\iota r^{\frac{\text{ロ}}{1}-}\iota r-\overline{\ovalbox{\tt\small REJECT}}\iota 4^{\sim_{\overline{|}}}$

還元を示す．

31$\iota A$$|$$o|0|0|0|0|0|0|0_{\ovalbox{\tt\small REJECT}}\circ|o_{I}o|0|0|0|0|0|0|o_{1}o|0_{y_{20}}$

スパイングラフ

––

$1$

$1$

$r\backslash$.

$r\tau$$|$$-\iota\alpha\underline{|}\iota A$
$1$

下部

$1$

$r$

’$‘$$d$酬匿慮

図 3: $n=4$ の場合の基本構成

スパイングラフ砺は以下の頂点と辺を持つ [1].

水平軸の正対する 2 つのリブを基点とした，2 つの垂直のスパイングラフは上下で対になっており，この$E(L_{k})$$\{(u_{i},u_{i-1}),$ $(sh,u_{i+1}),$,
2 つのスパイングラフをまとめて変数アンテナと呼ぶ．変数アンテナには 中の変数に対応したインデックスを左から順に割り当てる (以降， と表記する).
特に頂点嘱，をリブと呼ぶ．単位は水平軸のリブの位置を入れ換えることにより，各長配置において，スパイングラフは水平または垂直上部と下部を入れ換えることができる．便宜上頂点にの一通りの配置を持つ (図 2).
色を付け，入れ換えによる区別を明示的にする．変数
アンテナについての白頂点が上部にあるとき入のの状態を True , 黒頂点が上部にあるときを 2 値変数と状態を $Fal$ se とする．数式中では$V(L_{k})$$=$$\{u_{i}, u_{i}’, u_{i}’’|1\leq i\leq k\}\cup\{u_{0},u_{k+1}\}$$=$$(u_{i},u_{i}’)$$(u_{*}\cdot, u^{\dot{\prime}\prime})|1\leq i\leq k\}$$\phi$$A_{i}$$u_{1}^{\prime.\prime}(2\leq i\leq k-1)$$A_{i}$$A_{i}$$A_{:}$$A_{i}$

して使用し，図 4 の状態を $A=\{A_{1}, A_{2}, A_{3},A_{4}\}=$

図 2: スパイングラフ

32

節の還元

$n$

変数 $3CNF$ 式$\phi$の任意の 1 節 $C_{j}=(l_{L}\vee l_{C}\vee l_{R})$$(1\leq L<C<R\leq n,$フ$G_{C_{j}}$$L_{4}$$l_{i}=x_{i}$またはへの還元について述べる．

$\overline{x}_{\backslash })$からグラ

図 4: 変数アンテナの入れ換え

147のように記述する． の状態が，SAT トの接続に要するガジェットを壁とし，壁は並列に置への割り当てと対応する．かれたスパイングラフの組合せで構成されており，配$\{T, F, T, F\}$

上の変数

$x_{i}$$A_{i}$

水平軸と各変数アンテナに， の構成に対応して 置は図 6 に示す 1 通りのみである．これにより$C_{j}$$G_{C_{j}}$以下の規則でガジェットを追加する． は節内の の配置は変数アンテナの状態．及びストライカー，ハソートされた 3 つのリテラルのうち，中央のリテランガーの左右の選択を除いて，置き方が固定される．と対応していることに注意)
全体図は図 6 のようになる．
$(A_{C}$$)l/l_{C}$て構成できる．図中の◎頂点の入れ換えによって頂 はじめに補題 1 を証明する．の SS が上部に配置される状態の
題 1 証明点群 を▼の位置に移動させ，使用する配置点を選択することができる．ハンガーの頂点の配置場所を とき制限するためには他にもグラフが必要であるが，そが True
・規則 (1) で追加された頂点を有する$-$.
..の構造については全体図を参照されたい．
節 C ろに対応するグラフは，以上で定めた各ガジェットを接続して構成される． の各ガジェツ$G_{C_{j}}$$G_{C_{j}}$$O$$A_{i}$$\ovalbox{\tt\small REJECT}$$\nabla$$0$$\bullet-\bullet-\bullet\bullet||$

$0$

$0$

$0$
$0_{I}$$o|0|$;

規則 (2) で追加された頂点を蕎するが Falseのいずれかである．これは$|$OOOOOO$\circ-0-0-0-0-0-0-\delta-\bullet-0-O-O-\circ-0-O-O-O$$A_{i}$$A_{i}$

C ゐ内の肯定リテラル$C_{j}$$x_{i}$に True を割り当てる

内の否定リテラル銑に False を割り当てる

対応するため，リテラルを True にする割り当てと-致する．同様に，SS を下部に配置する状態と，リラルを False にする割り当てが一致するため，補口
題 が成り立つ$|$$l$‘$\tilde\tilde$$\sim$$\overline{\gamma}$$4^{--\Psi^{;}}:..:;::::\nabla::\backslash \backslash \nabla-.v-\nabla..:;:^{O..\dot{\nabla}..0_{:}};\underline{v-\nabla-\nabla^{\dot{j}}|,\downarrow.|\iota^{\nabla}d;:::|_{\urcorner}..:|’|}:::1$$\bullet-\bullet-\bullet\bullet||oooo_{L4}^{:_{\text{▼_{}t}^{\vee}.\cdot O_{-:}}}[..r.\backslash ..:;:_{\underline{\iota}_{\wedge\backslash }};:::::::$$F^{\mathfrak{k}}$$’\backslash X$$\grave{j}$$1$に補題 2 を記明する．
題 2 証明 SS 以外のガジェットは上下どちらの配図 5: ハンガーの構成$is\{|$$\mathscr{C}$

点を埋めるかが固定されている．下部の配置点を埋148

図 6: $\{x_{1},x_{2},x_{3},x_{4}\}$ 上の$\delta$の$C_{j}=(x_{2},\overline{x}_{3},\overline{x}_{4})$から変換したグラフ

めるガジェットは DS $(n-3$ 個 , 下ハンガー (1 個),単位長配置を成立させるためには SS を上部に 1 個，規則 (6) による頂点 (1 個) であり，計 $n-1$ 個の配下部に 2 個配置することが必要条件である$)$

口置点が使用される．上部の配置点を埋めるガジェット
は，下部と同様のガジェットに加えて右端の配置点を最後に補題 3 を証明する．
埋める頂点である．よって計 個の配置点が使用さ 補題 3 証明 アンテナ $(A_{L}, A_{C}, A_{R})$ の SS の位置がれる．この時点で，上部で使われていない残りの配 (上，下，下), (下，上，下), (下，下，上) となる状
置点は 1 つ，下部の残りの配置点は 2 つである．態 $A$ について考察する．上記 3 通りの SS の上下の位$n$

残りのガジェットの 3 個の SS は，変数アンテナの置に対して，単位長配置がそれぞれに丁度 1 つずつ状態を変えることによって上下どちらの配置点を埋存在する (図 7,8,9). 図に示した以外の配置を持ためるかが選択可能である．配置点の数から，$G_{C_{j}}$でないのは，配置方向が固定されているストライカー

149
33
$n$

$3CNF$ 式$\phi$から木 $G_{p}hi$ への還元

変数 $m$ 節の $3CNF$ 式に変換し，各る $(10(a))$ .

$G_{C_{j}}$$\phi$

中の全ての節 C ろを

$G_{C_{j}}$を列上に並べて同一の壁で接続す$ji;:. \int^{--}_{\grave{I}}_{i}:^{1}j’\#;;;:.,|_{A_{i2}}^{A_{i.1}}$

図 7: ストライカー (上，下，下) の単位長配置$| \int|$$|_{-}\ldots.i(:::\backslash$

(b)

(a)

図 10: (a) 各$Gc_{j}$の接続(b) 状態の統一

図 8: ストライカー (下，上，下) の単位長配置の変数アンテナを入，j と表について変数アンテナ記する．今，任意のここで$A_{i}$$G_{C_{j}}$$i$$A_{i,1},A_{i,2},$ $\cdots,A_{i,m}$はそれぞれの状態に関連性がな

い．これは SAT 式 においては，異なる節$\phi$$C_{j},C_{j’}$中に存在する変数簸について，節ごとで への割り当てが違うことを意味する．そこで本小節では，任の意の について変数アンテナのグラフ
状態を統一 図 $10(b))$ するための，各構造の変更点について述べる．
図 9: ストライカー (下，下，上) の単位長配置
はじめに，変数アンテナの構造について述べる．変数アンテナの構造を図 11 のように変更し，白頂点部から順番にガジェットを配置していくことで容易にを凸，黒頂点を凹とする．凸凹共に配置方法は図わかる．よって状態 $A$ に対応する $f$ が丁度 1 つ存在
11 に示す一通りしかない．配置点を $w’,$ $w”,$ $b’,$ のする．また が与えられたとき，対応する $f$ は図 7,左右，ストライカーを追加する頂点を $w’,$ とする
8, 9 の表を参照することで の線形時間で求められ$x_{i}$$A_{i,1},$ $A_{i,2},$ $\cdots,$ $A_{i,m}$$i$$($$G_{C_{j}}$$b”$

$A$

$b’$

$n$

る

口定理 1 証明 補題 2,3 から，“SS を丁度 1 つ上に配置する状態” である $A$ からの単位長配置 $f$ へ，の線形時間で計算可能な全射が存在することがわかる．また補題 1 より，“SS を丁度 1 つ上に配置する状態” である $A$ は，“節内のリテラルが丁度 1 つ Trueとなる割り崇て” である に一致する．よって定理 1が成り立つ
口$G_{C_{j}}$

$x$

$n$

ことで，このアンテナへの変更後も前小節の$G_{C_{j}}$と同じく l-in-3 SAT の 1 節と同一の性質を持つ．

次にハンガーの構造を変更する．今，変数アンテ
ナ $A_{1,j}-A_{1,j+1}$ の間には，C ろの下ハンガーと $C_{j+1}$の上ハンガーとして使われている 4 つの水平のスパイングラフが存在する (図 12). これらを以下のように変更する (図 13).

.

変数アンテナとスパイングラフの間の空白座標の行を詰める．

・各スパイングラフの間には空白座標の行を 1 つ用意する．

150
$1$

$1$

$1$

$1$

$1$

$1$

$|$

$’$

$1V$

–ロ

$T0-\square -\square -\square -\square -\square -\square -\square -\square -\square$

OOOOO

.

$\mathcal{W}$OOOOO$\square$$-0-0-0-0-0-0-0-0-0-0-0-$
’$0$

$0$

$0$

$b$

鷺–.–
– $\cdot$

–$0$

$0$

$\cdot$ – $\cdot$ – $\cdot$$\cdot$ – $\cdot$ – $\cdot$ – $\cdot$– $\cdot$ – $\cdot$ – $\cdot$ – $\cdot$– $\cdot$

$0$

$0$

$0$

$0$

$-!-\cdot-\cdot-\cdot-\cdot$– $\cdot$

–$0$
2,$b$

–穏$\cdot$ – $\cdot$ – $\cdot$ – $\cdot$–$\cdot$ – $\cdot$ – $\cdot$ – $\cdot$–$\cdot$ – $\cdot$ – $\cdot$–$\cdot$ – $\cdot$–$\cdot$ – $\cdot$ – $\cdot$ – $\cdot$$\ldots$– $\cdot$ – $\cdot$$!$–$\cdot$ – $\cdot$$!$

図 11: 凹凸形状の変数アンテナ$G_{C_{j}}$$G_{C},1$

図 13: トランスミッターの構成とその配置

図 12: 変数アンテナ間の 4 つの水平スパイングラフ.

変数アンテナの中心点の 座標を $X$ として，座標が $X-1,X,$ $X+1$ であるスパイングラフの
$x$

$x$

$G_{C_{j}}$リブの片側に頂点を 1 つ追加 (図 13 の▲，▼)以上のガジェットをトランスミッターとする．

$A_{1,j}-$間の構造は図 13 のようになり， と間の配置は (a),(b) に示す 2 通りのみである．トラン$A_{1,j}$$A_{1,j+1}$$A_{1,j+1}$

図 14: トランスミッターの問題点
スミッターによって変数アンテナの動きが制限され，の凸部と $A_{1,j+1}$ の凹部が必ず向かい合うことにと対を数アンテナを $2n$ 個設置し，論理変数と $A_{1,j+1}$ の状態が同じになる．
なる．すなわち$A_{k}(k=1,3, \ldots, 2n-1)$ をダミー変数ア応させる．
$C_{j}=(l_{L}\vee l_{C}\vee l_{R})$ について $C$ が奇数であるとき，$A_{1,j}$$x_{i}$$A_{2i}$$A_{1,j}$

GC ろの上ハンガーの対称軸と変数アンテナの中心点が同じ列上となる．同様に$n$ンテナとし， のどの節にも使われていない変数に$\phi$$A_{(c+1)/2,j}$が奇数である

とき，下ハンガーの対称軸と変数アンテナ $A_{(n+1)/2,j}$の中心点が同じ列状となる．以上の場合はトランスミッターが配置できない．(図 14).
これを解決するために 1 つの節グラフに対して変対応しているものとして扱う．つまり，全てのダミー変数アンテナは DS が付与される．この変更により，ハンガーの対称軸は変数アンテナの中心点の列と重ならない．さらに$G_{C_{j}}(2\leq j\leq m)$の上ハンガーの延長線上に，壁の右内側に接続するスパイングラフ

151
元である． は木構造となっているため，以下の定を配置する．

$G_{\phi}$以上の変更で，全ての$A_{i,j}-A_{i,j+1}$間に 4 つのスパイングラフが存在することになり，それぞれに前途のトランスミッターを配置することで，任意の につ$i$

いて $A_{i,j}(1\leq j\leq m)$ の状態を揃えることができる．のダミー変数アンテナを凸凸の組合せにすることで，ダミー変数アンテナの状態を固定する (図 15).
また理が成り立つ．

定理 3 木の単位長配置の関数問題は ASP 完全である．

$G_{C_{1}}$4まとめl-in-3 SAT から最大次数 4 の木の単位長配置への多項式時間 ASP 還元を示すことにより，上記問題が ASP 完全であることを証明した．この問題から
Vnicius らの還元 [2] を行うことで，最大次数 3 のグラフについても ASP 完全性が証明できる．また，単位長配置の一般化である二次元バンド幅問題 (全て以下になる配置が可能かどうかの判定 についても，木の関数問題の ASP 完全性が証明の辺コストが$k$$)$できる．

今後の課題として，最大次数 3 の木の単位長配置が ASP 完全であるかどうかの調査が挙げられる．

参考文献

ダミー変数アンテナ列[1]図 15: ダミー変数アンテナの固定以上の$n$

変数 $m$ 節 $3CNF$ 式

れたグラフを定理 2$\phi$$G_{\phi}$$\phi$からの変換で得らとして，以下の定理が成り立つ．

を充足する割り当て$x$から$G_{\phi}$の単位長配

置 $f$ へ，$n,$ $m$ の線形時間で計算可能な全単射が存在する．

証明の$x$

定理 1 より， を充足する割り当て$\phi$$x$は，任意N. Bhatt and S. Cosmadakis. The complexity of minimizing wire lengths in VLSI layouts.
Inf. Process. Lett., Vol. 25, pp. 263-267, June$S$$S$

1987.
[2] Vinicius G. P. de Sa, Guilherme Dias da Fonseca, Raphael C. S. Machado, and Celina
M. Herrera de Figueiredo. Complexity dichotomy on partial grid recognition. Theor.
Comput. Sci., pp. 2370-2379, 2011.

に対して丁度 1 つの単位長配置を持つので，[3] T. Yato and T. Seta. Complexity and Completeの単位長配置 $f$ も丁度 1 つ存在すに対応する
ness of Finding AnotherSolution and Its Appli$G_{C_{j}}$$G_{\phi}$る．また，異なる割り当て $x,x’$ に対応する $f,f’$ は，いずれかの変数アンテナの状態が異なる (凹凸の向きが変わる) ため，必ず $f\neq f’$ となる．よって，SATの解と単位長配置の解は一対一対応である．
定理 1 より， から $G_{C_{j}}(1\leq i\leq m)$ の単位長配置が の線形時間で求められるので， に対応する
$x$

$x$

$n$

$G_{\phi}$$n$の $f$ は $n,$ $m$の線形時間で求められる．

付録
還元によって$\phi=C_{1}\wedge C_{2}\wedge C_{3}(C_{1}=(\overline{x}_{1}\vee\overline{x}_{2}\vee$$\square$

変数 $m$ 節の から間で行える (各cation to Puzzles. IEICE Trans. Fund. Elect.
Comm. Comp. Sci, Vol. 86, No. 5, pp. 10521060, 2003-05-01.

$\phi$$G_{C_{j}}$$G_{\phi}$への変換は $n,$ $m$ の線形時への変換が$n$$\overline{x}_{3}),$$C_{2}=(\overline{x}_{1}\vee x_{2}\vee\overline{x}_{4}),$ $C_{3}=(x_{1}\vee\overline{x}_{3}\vee x_{4}))$から得られると， の充足解の線形時間で，そ に対応する単位長配置を記載する．なお，SS が付与れを $m$ 回行う) ので，上記還元は多項式時間 ASP 還$G_{\phi}$$\phi$$(x_{1}, x_{2}, x_{3}, x_{4})=(T, F, T, F)$

された変数アンテナには二重線の囲いを付けている．

152

しし