グラフの交差数最小 2 層描画問題に対する分枝限定

グラフの交差数最小 2 層描画問題に対する
分枝限定アルゴリズム
丸田拓和
明治大学大学院
理工学研究科基礎理工学専攻情報科学系
計算理論研究室
2015 年 2 月 13 日
概要
グラフの h 層描画とはグラフの描画方法の一つであり，特定の基準をもとに頂点集合を
h 個の”層”として階層上に配置し，異なる階層間に限定した直線分で辺を描画することを
目的としている．単純にグラフの階層描画とも呼ばれる．このなかで，特に 2 部グラフに
限定したものはグラフの 2 層描画問題と呼ばれ，データの関連度を求めるバイクラスタリ
ングの分野や，遺伝子マッピング，コールグラフ等の応用がある．これらの応用先の多く
においては，人間による認識の向上や技術的な応用等の理由から辺同士の交差数が最小と
なる 2 層描画が求められている．このような問題は，頂点の取り扱い方により one-sided
crossing minimization（OSCM），あるいは two-layer crossing minimization（TLCM）
等と呼ばれている．
本論文では，グラフの交差数最小 2 層描画問題に対するアプローチとして，バックト
ラックにいくつかの下界を用いた分枝限定アルゴリズムを提案し，複数の入力に対する実
行速度からそれぞれの性能について検証した．また，整数計画法ソルバーを利用した整数
計画法による解法と，分枝限定法アルゴリズムの比較実験をすることで，多くのケースで
は分枝限定法よりも整数計画法による解法が高速であるということを示し，その特性か
ら，バックトラックによる探索を整数計画法による解法よりも高速に動作させることが困
難であるということを示した．さらに，その結果をもとに，LP 緩和から求まる下界と，
組み合わせ最適化アルゴリズムから求まる下界の値について比較実験し，切除平面法とな
りうる制約を加えることで下界の性能自体の向上ができる可能性について示した．
1
目次
第1章
はじめに
3
1.1
諸定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
グラフレイアウト問題 . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
交差数最小 2 層描画問題
6
2.1
グラフの描画における交差 . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
TLCM に関する先行研究 . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.3
その他関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
第2章
第3章
分枝限定法
10
利用する下界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
整数計画法
16
4.1
TLCM への定式化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.2
ILOG CPLEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.3
LP による下界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
実験
19
5.1
グラフの特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5.2
実験 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.3
実験 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
まとめ
28
3.1
第4章
第5章
第6章
参考文献
30
2
第1章
はじめに
グラフは，複数のオブジェクト同士の相互関係を抽象化した表現であり，対象となるオ
ブジェクトを頂点とおき，オブジェクト間が持つ関係を，頂点同士を結ぶ辺とおくこと
で，現実世界の様々なものをモデル化することができる．これらのグラフモデルを利用し
最適化問題を解くことは現実世界の多くの問題の解決方法として応用できるため，様々な
分野で広く研究が行なわれている．しかしながら，これらの問題の中には，多項式時間で
解を求めるアルゴリズムが発見されていない，もしくはある計算量理論による仮定の元で
は多項式時間で解を求めるアルゴリズムが存在しない問題も多く知られている．このよう
な問題については，特殊なインスタンスに対し高速に動作する，あるいは厳密解から許容
出来る範囲での実行時間ないし解を求めることができるようなアルゴリズムの設計や考案
が盛んに行なわれている．
グラフ描画問題 [7] はその一例であり，この問題では，入力として得られたグラフの構
造を人間が視覚的に理解しやすいように，頂点を点，辺を線として平面上あるいは空間上
の図形として表現する方法について考えられている．グラフを図形として描画する場合，
その形状はグラフの構造によって必ずしも一意に決定されるものではないため，入力とな
るグラフの構造に合った描画でなければ，人間による視覚的な理解を妨げるものになって
しまう．そのため，グラフ描画問題では，あるグラフが与えられた際に，そのグラフを単
純に視覚化するのではなく，いくつかの審美的基準をもとに，グラフの形状を調整して描
画する方法について考えられている．
グラフ描画問題の一つであるグラフの階層描画のうち，特に 2 部グラフを入力としたグ
ラフの辺同士の交差数を最小化する方法について考える．このような問題はグラフの最小
2 層描画問題と呼ばれ，頂点集合の頂点順序より生じる辺同士の交差数の最小化を目的と
している．そのため，この問題は最小な交差数を目的関数としたグラフレイアウト問題と
して定式化することができる．
本論文においては，グラフの最小 2 層描画問題に対するアプローチとして，素朴な
バックトラックに下界を用いて枝刈りしながら探索する分枝限定法アルゴリズムと，片
方の層の順序を固定し，もう一方の交差数の最小化を図る OSCM（One-Sided Crossing
Minimization）の下界を用いた動的計画法アルゴリズムを設計し，バックトラックにお
いて利用した 2 種類の下界それぞれと，動的計画法，および整数計画法ソルバーを用いた
3
解法との計算時間について比較実験を行ない，その結果から各手法の性能について考察し
た．また，整数計画法ソルバーの機能を利用し，LP 緩和によって LP 解を求めることで
得られた下界と，組み合わせ最適化アルゴリズムから求まる下界について，速度ではなく
下界値に対し比較実験を行ない，結果をまとめる．
1.1 諸定義
ここでは，グラフ描画問題を取り扱ううえで必要となるいくつかの用語と，表記方法
について定義する．本論文では，入力となる無向グラフ G において，G の頂点集合を
V (G)，辺集合を E(G) とそれぞれ表現する．また，G の頂点集合に含まれる頂点数を
|V (G)|，G に存在する辺の本数を |E(G)| とする．ここでグラフ G は単純な構造（多重辺
や自己ループを持たないもの）であるとする．G に含まれる頂点 v(v ∈ V (G)) の次数（v
に接続する辺の本数）を d(v) と表し，v の隣接点集合を N (v) と表す．G が単純な構造
である場合，d(v) = |N (v)| となる．
頂点 v の隣接点集合の定義は次のように頂点集合上に拡張できる．U ⊆ V (G) におい
て，N (U ) を
∪
v∈U
N (v) \ U と表す．また，G[U ] を U によって誘導される部分グラフ，
すなわち G[U ] = (U, {{u, v} ∈ E(G) : u, v ∈ U }) と表現する．特に，次数が d(v) = 1
となる頂点 v をリーフ（あるいは葉）と呼ぶものとする．
G の辺集合のうち，頂点 a と b を接続する辺を e(a, b) ∈ E(G) と表現する．このとき，
葉となる頂点に接続する辺をリーフ辺と呼ぶものとする．また，頂点を辿ることによって
得られる辺集合をパスと呼び，頂点 a から b につながるパスを P (a, b) と表す．本論文に
おいては，パス P (a, b) に関し a ̸= b（P (a, b) が閉路でないこと）を仮定する．
G が 2 部グラフである場合，V (G) を 2 分割する頂点集合 T, B ⊆ V (G), T ∩ B = ∅ が
存在し，G[T ] 及び G[B] のそれぞれに辺が存在しない．グラフ G が 2 部グラフであると
き，G の 2 分割を T (G), B(G) で表し，G を (T (G), B(G), E(G)) と表す．なお，特に断
りがない限り，取り扱うグラフ G は 2 部グラフであることとし，G の 2 分割 T (G), B(G)
の両方が既に与えられていることを仮定する．
U ⊆ V (G) において，長さ |U | の列に U の各要素がその列の中にちょうど 1 回ずつ現
れるもののことを U 上の順列と呼ぶ．ある頂点 u, v ∈ U の順序関係は u <U v あるいは，
u >U v として表現し，u <U v となる場合，u が v の前に現れるものとする．本論文にお
いては，2 部グラフの頂点分割 T (G) ⊂ V (G), B(G) ⊂ V (G)) において，T (G) に対す
る順序関係は <T あるいは >T によって，B(G) に対する順序は <B あるいは >B によっ
て決定されるものとする．今後，本論文に出てくる記法はこの定義に従うものとする．
1.2 グラフレイアウト問題
無向または有向グラフ G = (V (G), E(G)) において，V (G) の分割を V1 , V2 , · · · , Vh
とし，頂点集合 i(1 ≤ i ≤ h) おける頂点順列を，πi とする．このとき，ある関数値
f (π1 , π2 , · · · , πt ) を最小化，もしくは最大化する問題を h グラフレイアウト問題と呼ぶ
4
[10]．
本論文においては，特に h = 2 に限定したグラフについて着目し，2 分割した頂点集合
T (G), B(B) を層として平行に配置することを考える．このとき，T (G) と B(G) の頂点
順列から生じる辺同士の交差数の最小化を目的として問題を定式化する．この問題は，2
層グラフに対する辺交差数最小化や，交差数最小 2 層描画問題と呼ばれるが，具体的な定
義については第 2 章の中で示すものとする．
5
第2章
交差数最小 2 層描画問題
h 個の分割を持つグラフに対し，各分割 Vi (1 ≤ i ≤ h) の頂点をそれぞれ一直線上に配
置し，各頂点を点，各辺を直線分で描画する方法を，グラフの階層描画と呼ぶ．特に入力
を 2 部グラフにした描画，すなわち 2 階層で表される描画をグラフの 2 層描画と呼ぶ．こ
のとき，平行に配置された頂点集合は層と呼ばれ，特に断りがない限り，同一の階層内に
含まれる頂点間に辺が存在しないものとする．
入力となるグラフを階層描画として表現することで，データ間の繋がり階層的に示すこ
とができるため，直感的な構造の把握や認識の支援が期待されており，特に 2 層グラフに
おいては遺伝子マッピング [8] やコールグラフの自動描画 [9]，VLSI のレイアウト [6]，バ
イクラスタリング [1] 等の応用を持つことで知られている．しかしながら，グラフの描画
において，その構造を単純に描画しただけでは人間が認識しやすい形にはならないため，
特定の見やすさの基準（審美的基準）に従い，より良いレイアウトへと調整する必要が
ある．
グラフの審美的基準とは，描画されたデータがどの程度容易に認識できるかを指し示す
基準である．この審美的基準としては以下のようなものが挙げられる [11]．
• 頂点の重なりを可能な限り減らす
• 辺は可能な限り直線を用いる
• 辺の長さは可能な限り揃える
• 辺の交差数を可能な限り減らす
本研究では上記項目のうち，特に「辺の交差数を可能な限り減らす」ことに着目 [12]
し，他の基準についてはグラフ構造を作る過程で調整するものとする．
グラフの視覚化を目的としたバイクラスタリングやコールグラフの技術においては，グ
ラフの構造を容易に把握できることが求められているため，極力少ない交差数となる描画
の発見が求められる．このような課題に対し，2 層描画において最小の交差数となる描画
を見つける問題は交差数最小 2 層描画問題（two-layer crossing minimization : TLCM）
あるいは TSCM（two-sided crossing minimization）と呼ばれている．
6
2.1 グラフの描画における交差
審美的基準をもとに，G の頂点や辺を平面上に配置した描画を D(G) と表現する．
D(G) は，入力となるグラフ G に対し，T (G) の全順序 <T と，B(G) の全順序 <B の三
つ組みで定義される．このとき，ある層 L の順序において，u <L v({u, v} ∈ L(G)) であ
る場合,u は v よりも左に存在することを意味する．また，D において，端点を共有しない
2 辺が交点を持つことを 2 辺が交差すると表現する．交差は頂点集合内での順序によって
生じるものであり，({x, y}, {u, v}) において，u <T x かつ y <B v または，x <T u かつ
v <B y を満たすことで生じる．そのため，ある描画 D(G) に存在する全ての辺同士の交
差数の合計を cr(D(G)) とおくと，その値は
bcr(D(G)) =
∑
|{(x, y) ∈ E(G) : x <T u, v <B y}|．
{u,v}∈E(G)
となる．TLCM において，最適解とはこの bcr(G) が最小となる描画のことである．
辺同士の交差は，各層における頂点順序の相対的な位置によって生じるものである
ため，組み合わせ的に同値となる 2 つの 2 層描画 D(G1 ) と D′ (G2 ) が存在する場合，
bcr(D(G1 )) = bcr(D′ (G2 )) を満たすものとする．図 2.1 に同値な描画の具体例を載せる．
図 2.1
同値な組み合わせ 2 層描画を持つグラフの例
同値な描画において交差数は一致する
また，ある層 L において，任意の頂点 v ∈ L(G) \ {u} において，u <L v となるとき，
L(G) において u が最左に位置するという．また，u >L v となるとき，L(G) において u
が最右に位置するという．
上述の通り，2 層描画を始めとした階層グラフの描画問題では，同階層内にある頂点の
相対的な配置，すなわち各層にある頂点順序によって変化することになるため，同階層
内にある 2 頂点を入れ替えることで初めて交差数が変化する．TLCM では，同階層内に
存在する 2 頂点間の順序入れ替えによって，辺交差が最小となる描画を求めることにな
るが，総当たりで最適となる並び順を求めようとすると O(|T (G)|!|B(G)|!) の計算時間が
かかるため現実的な時間では解を求めることができない．そのため，様々なアプローチ
7
によってより高速に解を導く方法や特殊なケースに対する解法などが盛んに研究されて
いる．
2.2 TLCM に関する先行研究
TLCM は h 個の分割を持つ階層グラフに対し，交差数が高々 k となるような h 層描
画を求める h-layer crossingminimization と呼ばれる問題のうち，h = 2 層に限定した特
殊なケースである．h-layer crossing minimization は Dujmović らの研究 [16] によって，
h + k をパラメータとした際に，FPT であることが証明された．また，同論文によって
3
2O((h+k) ) n のアルゴリズムも示されている．しかしながら，このアルゴリズムは非常に
高度であり，実装の観点から h を 2 に限定した TLCM を解くアルゴリズムの設計は有意
義である．
Garey と Johnson の研究 [13] から，TLCM は NP 完全であることが知られており，
h-layer crossing minimization の特殊ケースであることからパラメータ容易である．小林
らの研究 [2] から，TLCM について初めてのカーネル化 [27] が与えられ，また，同論文か
ら交差数 k をパラメータとした 2O(k log k) + nO(1) 時間の FPT アルゴリズムが示された．
中江の研究から Zheng と Buchheim による TLCM の整数計画法に対しカーネル化を用
いることで，限定されたインスタンスにおいての高速化できることが示された．
また，グラフを木に限定した場合においては，Shahrokhi らの研究 [5] により多項式時
間で求まることが示されている．本研究においては，これらとはさらに別のアプローチと
して，単純なバックトラックに対し，下界により探索範囲を限定する分枝限定法アルゴリ
ズムについて，速度，および下界そのものの性能についての結果をまとめる．
2.3 その他関連研究
TLCM の他にも 2 層描画の手法はいくつか知られている．one-sided crossing minmization(OSCM) は TLCM 同様に頂点順列の入れ替えによる交差数の最小化を目的と
している．ただし，この問題では入力となる 2 部グラフ G のうち，指定された層の順列
を固定し，もう一方の層の頂点順列のみを変化させることで交差数の最小化を目指して
いる．OSCM は NP 困難であり，OSCM に対する FPT アルゴリズムは TLCM よりも
多くの研究結果が知られている．[15, 19, 18] 最初の FPT アルゴリズムが [15] が与えら
れ，[19] によって高速な FPT アルゴリズムと辺数 O(k 2 ) のカーネルが与えられた．さ
らに，[18] と [17] が頂点数 n のグラフに対し，それぞれ実行時間 2O(
準指数関数の FPT アルゴリズムと，実行時間 O(3
√
2k
√
k log k)
+ nO(1) の
+ n) の準指数関数の FPT アルゴ
リズムを与えた．OSCM においては片面を固定するという問題の仕様から，OSCM では
TLCM の最適解（あるいは近似解）を得ることができない入力例も存在する．
また，OSCM は多階層描画アプローチとして知られる Sugiyama，Tagawa，Toda[14]
の研究において，等価なフィードバック辺集合問題として定式化されている．
その他の 2 層描画を問題としては，two-layer planarization（TLP）が知られている
8
[20]．TLP は OSCM や TLCM とは異なり，入力となるグラフから辺を取り除くことで，
交差なしの 2 層描画を探す問題である．この問題も TLCM 同様 FPT 容易であることが
知られており [21]，頂点数 n のグラフから高々 k 本の辺を取り除くことを考えた際に，
O(k · 3．562k + n) の実行時間で解くアルゴリズムが知られている [22]．また，TLP につ
いては辺数 O(k) のカーネル化について知られている [21]．
9
第3章
分枝限定法
既に述べたように，愚直に全通りの組み合わせを調べる場合，|T (G)|!|B(G)|! の探索が
必要になってしまう．しかしながら，現在探索している組み合わせに対し，最低でも必ず
発生する交差の数（下界）を求めることができるのであれば，余分な探索の切り捨てをす
ることができると考えられる．このように，探索をするに際に，下界や上界の値から，最
適でない組み合わせが見つかった時点で以降の探索を切り捨てていく手法を分枝限定法と
いう．このような手法においては，間違った頂点選択を効率よく切り捨てられるような優
れた下界が望まれている．
本研究では，分枝限定法に用いられる様々な下界を設計し，それぞれの性能を比較する．
3.1 利用する下界
本研究では以下の 3 種類の下界を用いて枝刈りを行なう．
1. 最短経路より求まる辺素なパスとその他の辺の交差
2. OSCM の下界
3. 順序確定した頂点対とその他の頂点に接続する辺同士の交差
3.1.1 最短経路より求まる辺素なパスとその他の辺の交差
頂点選択によって見つかるパス同士の交差を考える．既に選択されている B(G) 層の頂
点を始点とし，T (G) 層の頂点に到達するパス同士は，各層の頂点順序によって交差を生
じる．
T (G) 層の最右の頂点を v とおき，B(G) 層の頂点を左から u1 , u2 , …, um (m = |V (B)|)
とおく．また，u1 , u2 , …, um から v へつながる c 本の辺素なパスを P1 , P2 , …, Pc とお
き，Pi の始点より左にある uj の集合を Ui とおく．この時辺 (x,y) は，以下の条件を満
たすならば Pi と少なくとも一回の交差する．
x, y ∩ (Ui ∪ V (Pi )) = ∅
10
図 3.1 にて，辺素なパスの例を示す．図 3.1 の頂点 u1 を起点とするパス P1 ではパス上
にある辺（図上の青い線）と，式から求まる辺（図上の緑色の線）は交差する．同様に，頂
点 u2 を起点とするパス P2 においても，パス上の辺（図上の赤い線）と，式から求まる辺
（図上の緑色の線）が互いに交差する．この時，辺素なパスという前提から，各パスと条
件を満たす辺同士に生じる辺は，互いに独立した問題として取り扱うことができるため，
グラフ全体としては，各パスに対する交差の総和を下界として取り扱うことができる．
図 3.1
辺素なパスの例
ただし，(x, y) が Pj (i ̸= j, 1 ≤ j ≤ h) に含まれる場合，重複して数えないものする．
本手法においては，下界に用いる辺素なパス集合 P1 , P2 , · · · , Ph を dijkstra 法による最短
経路から求めるものとする．
3.1.2 OSCM の下界
この下界を用いた探索では，片方の層にある頂点を優先して割り当てていき，もう一方
の層は優先されている層の頂点の順序が全て決まるまで探索しない．ここで優先される層
を固定層，もう一方を自由層と呼ぶこととする．優先される層の探索において，頂点を一
つ確定させるたびに自由層の任意の 2 頂点間で必ず生じる全ての交差の総和を求め，その
値が現在の最小交差数以上なった時点で探索を打ち切る．自由層（F (G) 層）における任
意の 2 頂点間で必ず生じる交差数とは，ある頂点 u, v において，選択済みの頂点に接続す
る辺同士の交差数と，u, v のうち左側にある頂点から未選択の頂点につながる全ての辺と
の交差の和の中で，頂点順序を u <F v とした場合と，頂点順序を v <F u とした場合の
小さい方の交差数の事である．この手法は，論文 [23] にて似たアプローチがされている．
11
図 3.2
黒い直線間に生じる交差と，灰色の直線との交差の総和が小さい方が下界
この例においては，自由層の 2 頂点を u <B v と置いた場合の交差数が下界となる
また，この下界を用いた探索によって，固定層の全ての頂点順列が求まった場合，自由
層の最適な配置は動的計画法によって求めることができる．
ここで用いる動的計画法のアイデアは Bellman[24]，および Held-Karp[24] の巡回セー
ルスマン問題（traveling salesman problem ： TSP）に対する結果を応用したもので
ある．
TSP は，n 都市からなる集合とその都市間の距離が与えられたとき，ある都市を始点に
総移動距離が最小となるように，ちょうど 1 回ずつ全都市を訪問し，始点の都市に戻る経
路を求める問題である．この問題は，総移動距離が最小となる訪問順列を求める問題とし
て考えることができるため，交差数の最小化を目的関数に置き換えることで，片面の最適
な順序割り当てを求める問題として考えることができる．
本研究では，Bellman，Held-Karp の結果にある 2n · n2 時間で TSP の解を導く動的計
画法を利用する．
12
3.1.3 頂点の選択により生じる交差
バックトラックによる頂点の選択を， T 層の頂点を右から，B 層の頂点を左から交互
に行なうことを考える．この時，次に示す辺の交差を求めることができる．
• 両端点の頂点順列が決まっている辺同士の交差
• 両端点の頂点順列が決まっている辺と両端点の頂点順列が未決定の辺の交差
• 両端点の頂点順列が決まっている辺と片方の頂点順列のみが決定している辺の交差
• 片方の頂点順列のみが決定している辺同士の交差
• 両端点の頂点順列が未決定の辺と片方の頂点順列のみが決定している辺の交差
このように分類された頂点と，選択された頂点から定まる辺の関係を図 3.3 に示す．図
3.3 において，赤い四角は頂点順序の決定した頂点集合，青い四角は頂点順序の決定した
頂点集合をそれぞれ示す．また，各頂点集合の間に引かれる辺については，赤い辺を両端
点が順序決定した辺，青い辺を両端点の頂点順序が未決定の辺，そして緑の辺を片方の辺
のみ頂点順序の定まった辺として表現する．これらの辺同士の交差を計上し，下界として
用いる．
図 3.3
頂点選択による頂点と辺の分類
それぞれについては次に説明する．
両端点の頂点順列が決まっている辺同士の交差
両端点が決まっている辺同士の場合，各層にある任意の頂点順列が一意に決まるため，
交差数を計上することができる．
両端点の頂点順列が決まっている辺と両端点の頂点順列が未決定の辺の交差
探索の順序から，T (G) 層においては，順序が決まっている頂点 u と順序が未決定の頂
点 x は常に x <T u の関係を満たす．同様に，B(G) 層においては，順序が決まっている
頂点 v と順序が未決定の頂点 y が v <B y の関係を常に満たす．そのため，頂点順序が決
まっている任意の辺 e(u, v) と頂点順序が未決定の任意の辺 e(x, y) は必ず交差する．
図 3.5 において，赤い辺と青い辺同士は必ず交差を生じる．
13
図 3.4 両端点の頂点順列が決まっている辺同士の交差
図 3.5
両端点の頂点順列が決まっている辺と両端点の頂点順列が未決定の辺の交差
両端点の頂点順列が決まっている辺と片方の頂点順列のみが決定している辺の交差
両頂点順序が決まっている辺 e(u, v) と，片方の頂点順列のみが決定している辺 e(x, y)
の交差について考える．ここで e(x, y) において，頂点 x のみ頂点順序が確定しているも
のとする．
探索の順序から，探索順序が決まっている任意の頂点 v と探索順序が決まっていない任
意の頂点 y は常に v <B y の関係を満たす．そのため，y は仮想的に任意の v より右側に
位置する，順列の決定した頂点として取り扱うことができるため，厳密に交差を求めるこ
とができる．同様に，x が未決定の頂点であるとした場合には T (G) 層において x <T u
の関係を満たすことから，x を仮想的に任意の u より左側に位置する頂点として取り扱
うことができることから，やはり厳密に交差を求めることができる．
図 3.6 において，具体的な例を示す．
この図の場合，T 層の緑の頂点集合は，T 層の赤い頂点集合の最左の頂点 5 よりも常に
左に存在する．そのため，これらの頂点は全て頂点 5 よりも左に存在する頂点として取り
扱うことができる．同様に，B 層の緑の頂点集合は，B 層の赤い頂点集合の最左の頂点 6
よりも常に右に存在するので，これらの頂点についても全て頂点 6 よりも右に存在する頂
点として取り扱うことができる．
14
図 3.6 両端点の頂点順列が決まっている辺と片方の頂点順列のみが決定している辺の交差
片方の頂点順列のみが決定している辺同士の交差
これらの辺は OSCM の下界である 3.1.2 を適用できる．図 3.7 にあるように，自由層・
固定層が逆転しても適用することができる．
両端点の頂点順列が未決定の辺と片方の頂点順列のみが決定している辺の交差
これらの辺についても，片方の頂点順列のみが決定している辺同士の交差と同様に，
OSCM の下界である 3.1.2 を適用できる．
この例についても，図 3.7 に示される通り，自由層・固定層が逆転しても適用可能で
ある．
図 3.7
片方の頂点順列のみが決定している辺同士の交差
および両端点の頂点順列が未決定の辺と片方の頂点順列のみが決定している辺の交差
以上の下界を用いることで，バックトラックアルゴリズムにおいて，探索を効率よく切
り捨てられるため，より高速に解を導くことが期待される．
また，両端点の頂点順序が未決定の辺同士の交差については現状として良いものが見つ
かっておらず，一般的な 2 部グラフの下界である bcr(H) ≥ |E(H)| − |V (H)| + 1（H は
G の誘導部分グラフ）や K2,2 によって得られる値を利用している．
15
第4章
整数計画法
TLCM の解を求める手法の一つに，インスタンスを整数計画問題に定式化し，整数計
画法によってその問題を解くことで解を導く方法が知られている．整数計画問題とは，最
適化問題の一つであり，特定の集合 S から定義される関数 f を最小化，あるいは最大化す
るような解ベクトル x ∈ S を求める問題である．この時，関数 f (x) を目的関数と呼び，
f (x) の条件を満たす解ベクトルを実行可能解と呼ぶ．なお，実行可能解のみを含む領域
は実行可能領域と呼ばれ，その範囲は与えられる制約条件によって決定される．
最適化問題においては，最適値と呼ばれる目的関数の最小値（あるいは最大値）を達成
する実行可能解の発見が要求される．このような実行可能解は最適解と呼ばれ，実行可能
領域上に存在する．
最適化問題において，目的関数が線形関数であり制約条件式を線形関数の等式と不等
式によって記述したものを線形計画問題と呼び，線形計画問題を解く手法を線形計画法
（LP:liner programming）と呼ぶ．特に，線形計画問題において解ベクトル x の各要素の
値を整数に限定したものを整数計画問題と呼び，整数計画問題を解く手法を整数計画法
（ILP：integer linear programming）と呼ぶ．本研究では参考文献 [3] の手法を利用して
整数計画問題へ定式化するものとする．
4.1 TLCM への定式化
この節では，入力となる 2 層グラフの整数計画問題への定式化について考える．
2 層グラフ G において，T (G) の頂点数を nT ，B(G) の頂点数を nB とおき，T (G) =
{t1 , t2 , . . . , tnT }，B(G) = {b1 , b2 , . . . , bnB } とする．また，D を G の任意の 2 層描画と
T
する．このとき，T (G) の異なる頂点 ti , tj について，D において ti <T tj ならば δij
= 1，
T
T
T
tj <T ti ならば δij
= 0 とする．定義より δij
= 1 − δji
となる．B(G) 側の頂点 bi , bj に
B
関しても δij
を同様に定義する．
ここで G の任意の頂点 v ∈ V (G) の隣接点集合を N (v) とすると，TLCM の目的関数
と制約条件は次のように定義できる．
16
目的関数:
min .
bcr(D) =
n∑
B −1
nB
∑
∑
∑
T
B
T
B
δkl
· δji
+ δlk
· δij
(4.1)
i=1 j=i+1 tk ∈N (bi ) tl ∈N (bj )
制約式:
T
T
δkl
+ δlk
= 1 (1 ≤ k < l ≤ nT )
B
B
δij
+ δji
= 1 (1 ≤ k < l ≤ nB )
T
T
T
0 ≤ δij
+ δjk
− δik
≤ 1 (1 ≤ i < j < k ≤ nT )
B
B
B
0 ≤ δij
+ δjk
− δik
≤ 1 (1 ≤ i < j < k ≤ nB )
T
B
δkl
, δij
∈ {0, 1}
辺 (tk , bi ) と辺 (tl , bj ) が D で交差するための必要十分条件は，tk <T tl かつ bj <B bi ，
T
B
または tl <T tk かつ bi <B bj であるため，実行可能解は制約式 δkl
· δji
= 1，ま
T
B
たは δlk
· δij
= 1 を必ず満たす．そのため，式 4.1 は整数計画問題においては正し
く D の交差を数えると言える．また，上の制約式はそれぞれ頂点対に対し全順序関
T
B
= 1，
係の反対称性と推移性，変数の整数性を保つ．そのため，制約式には δlk
+ δij
T
T
T
+ δjk
− δik
≤ 1 (1 ≤ i < j < k ≤ nT ) が含まれる．ここで，式 4.1 を次のよ
0 ≤ δij
うに置き換える事を考える．
n∑
B −1
bcr(D) =
nB
∑
∑
∑
B
T
B
T
· δij
+ δlk
· δji
δkl
i=1 j=i+1 tk ∈N (bi ) tl ∈N (bj )
n∑
B −1
=
nB
∑
∑
∑
T
B
T
B
δkl
· (1 − δij
) + (1 − δkl
) · δij
i=1 j=i+1 tk ∈N (bi ) tl ∈N (bj )\tk
n∑
B −1
=
nB
∑
∑
∑
T
B
T
B
δkl
+ δij
− 2δkl
· δij
(4.2)
i=1 j=i+1 tk ∈N (bi ) tl ∈N (bj )\tk
T
B
式 4.2 をの線形化するために，δkl
· δij
を新しい変数 βklij で置き換えることを考える．
T
B
ただし，新たに加えた変数 βklij において，δk,l
· δi,j
= βk,l,i,j を保障するために制約式に
T
βklij − δkl
≤ 0 (k ∈ N (i), l ∈ N (j) \ k, 1 ≤ i < j ≤ nB ) を追加するものとする（B 層
についても同様）．
目的関数:
min .
bcr(D) =
n∑
B −1
nB
∑
∑
∑
T
B
δkl
+ δij
− 2βklij
i=1 j=i+1 k∈N (i) l∈N (j)\k
制約式:
T
βklij − δkl
≤ 0 (k ∈ N (i), l ∈ N (j) \ k, 1 ≤ i < j ≤ nB )
B
βklij − δij
≤ 0 (k ∈ N (i), l ∈ N (j) \ k, 1 ≤ i < j ≤ nB )
17
(4.3)
T
T
δkl
+ δlk
= 1 (1 ≤ k < l ≤ nT )
B
B
δij
+ δji
= 1 (1 ≤ i < j ≤ nB )
T
T
T
0 ≤ δij
+ δjk
− δik
≤ 1 (1 ≤ i < j < k ≤ nT )
B
B
B
0 ≤ δij
+ δjk
− δik
≤ 1 (1 ≤ i < j < k ≤ nB )
T
B
δkl
, δij
, βklij ∈ {0, 1}
4.2 ILOG CPLEX
本研究においては，汎用整数計画問題ソルバーである ILOG CPLEX 12.6[4] を利用
する．ILOG CPLEX（以下，CPLEX）とは，ILOG より提供される有償の数理計画法
ソルバーであり，一般の整数計画法を定義することによって厳密解を得ることができる．
また，CPLEX では，Java を始め一般に知られるプログラム言語に対するライブラリが
与えられているため，実験においてこれらの環境を利用するものとする．CPLEX におい
て動作するアルゴリズムについては，詳細が公開されていない．しかし，一般に切除平面
法を用いた LP をベースとした分枝限定法による手法が用いていると考えられている．切
除平面法は，制約条件の不等式と整数変数の条件によって導かれる不等式（カット）を利
用するものであり，LP 解が整数解となるように挿入される．このようなカットが生じる
ように，問題の性質に合わせた制約を加えることにで，通常の解法よりも高速に動作する
ことが期待される．
4.3 LP による下界
TLCM における実行可能解は，同一層内における任意の 2 頂点間の相対配置 δa,b に
よって定義づけられるため，整数計画法に定式化する場合においては (0, 1) のどちらかに
よって値が確定する．しかし，この整数制約を取り除くことで，実行可能解は 2 頂点間に
おける LP 解を得ることになる．LP 解では，ある層 L の任意の 2 頂点対 {a, b} に対し，
L
δa,b
は 3.3 における青い集合に含まれる頂点以外の全てを包含することができるため，制
約式によって確実に生じる辺同士の交差数を求めることができると考えられる．
18
第5章
実験
各下界を用いた手法の性能を調べるために，複数のグラフについて TLCM を解く実験
を行なった．この実験では，各下界を用いたアルゴリズムによって，決められたグラフに
対する TLCM を実行し，その実行時間と再帰の深さを調べることでそれぞれの下界の性
能を比較する．また，ソルバーにより整数計画法の式を用いて得られる，LP による下界
の性能について述べるものとする．
なお本論文においては，次に示すような特性を持つグラフを入力として利用する．
5.1 グラフの特性
本実験で利用するグラフは次のような特性を持つものである
1. セミクリークグラフ
2. セミクリークグラフと同じ辺密度のランダム生成グラフ
3. 非常に辺密度の低いグラフ
4. 非常に辺密度の高いグラフ
各グラフについては具体例を交え説明する．
また，本論文において，辺密度とはどの程度完全グラフに近いかの指標であり，次の式
で表される．
|E(G)|
|T (G)| · |B(G)|
これにより，完全グラフの辺密度は 100% になる．また，辺の数が頂点に対し少なければ
辺密度は下がる．
5.1.1 セミクリークグラフ
セミクリークグラフとは，グラフの中に局所的にクリーク（あるいは，クリークに近い
ほど高い辺密度）となる部分が存在するグラフである．具体的には図 5.1 のようになる．
本実験においては，次のような手法でこのグラフを生成する．
19
図 5.1 セミクリークなグラフの例
1. 正規分布を用いて各層を M 個の頂点集合に分割
2. 各頂点集合に含まれる頂点には 90% の確率で辺を引く
3. 連結性を保持するために，他の各集合間に 1 本必ず辺を引く
4. 各頂点間に 0.5% の確率でランダムに辺を引く
図 5.2 に上記グラフの生成方法のイメージを載せる．
図 5.2 グラフ生成のイメージ
関連研究としては，[1] にあるような biclustering ではこのようなグラフの最小化が求
められている．
5.1.2 セミクリークグラフと同じ辺密度のランダム生成グラフ
ランダムグラフとは，各頂点間にランダムな確率で辺が引かれるグラフである．本実験
においては，セミクリークグラフとの性能比較ために，入力としてセミクリークグラフが
与えられ，元となるグラフと同じ辺密度になるように辺を引くものとする．具体的には図
5.3 のようになる．
20
図 5.3 ランダムなグラフの例
この例は，図 5.1 を入力としたランダムグラフ
5.1.3 辺密度の低いグラフ
辺密度の低いグラフとは，高い辺密度とは逆に非常に辺密度が低くなるように生成され
たグラフである．具体的には図 5.4 のようになる．
図 5.4
疎なグラフの例
本実験においては次のような形で生成する．
1. 連結性の保持目的に，グラフが木かパスになるように各頂点間に辺を引く
2. 各頂点間に 10% の確率でランダムに辺を引く
低い辺密度という特性から，最小交差が 0 になる描画が生まれやすい．また，このグラ
フの事を疎なグラフと呼ぶ．
21
5.1.4 辺密度の高いグラフ
辺密度の高いグラフとは，辺密度が 90% を超えるようにランダムに辺を引いたグラフ
である．高い辺密度という特性から，完全グラフに非常に近くなる．具体的には図 5.5 の
ようになる．
図 5.5
密なグラフの例
また，このグラフの事を密なグラフとも呼ぶ．
5.2 実験 1
本実験においては，|T (G)| = |B(G)| となる連結グラフを入力として取り扱う．ただ
し，片面の頂点数が 5 程度の 2 層グラフでは，特定のアルゴリズムを除き性能による大
きな差が得られなかったことから，今回の全ての実験において取り扱うグラフの頂点数
は片面 6 以上 15 以下とする．そのため，実験対象のグラフの全頂点数の組み合わせは
12,14,16,18,20,22,24，26,28,30 となる．このようなグラフを，4 種類の特性毎に，各頂点
数につき 100 件ずつ，計 4000 件のランダムデータとして生成し，TLCM を実行する．こ
のとき，全てのデータについて，実行時間が 600000[ms] 以上かかるものについては，計
測不能として実験操作を中断するものとする．また，実験において全てのデータを載せて
しまうと莫大な情報量となってしまうことから，100 件毎（片面の頂点数毎）の実験結果
の平均実行速度と再帰の深さの平均，解の発見失敗数を調べるものとする．
5.2.1 実験結果
本実験結果において，下界を下界 3.1.1 に設定したものを Path と呼び，同様に下界
3.1.2 を OSCM，下界 3.1.3 を Cross，CPLEX 12.6 による解法を IP とそれぞれ表現
する．
各実験結果を表にまとめる．なお，各表において，アルゴリズムが全テストケースに対
22
し計測不能を出力した場合には”–”によって表現するものとする．
セミクリークグラフ
セミクリークグラフに対する実験結果を表 5.1 にまとめる．
実験の結果から，速度の平均としては Cross の方が，OSCM よりも再帰が深いにもかか
わらず高速に動作していることがわかる．しかしながら，失敗数の合計で見ると OSCM
の方が高い性能を発揮していることがわかる．また，このようなケースの場合，頂点数が
大きなものになっても IP が非常に高速に動作していることがわかる．
表 5.1 セミクリークグラフに対する実行結果
Path
頂点数
再帰の深さ
OSCM
Cross
速度 [ms]
失敗数
再帰の深さ
速度 [ms]
失敗数
再帰の深さ
IP
速度 [ms]
失敗数
速度 [ms]
失敗数
n=6
830947
285.52
0
37.11
4.24
0
170.29
5.02
0
51
0
n=7
46632334
19976.3
0
72.3
14.9
0
390.72
16.42
0
57.44
0
n=8
–
–
100
133.59
51.86
0
800.26
51.69
0
90.23
0
n=9
–
–
100
201.1
173.41
0
1570.18
158.35
0
154.18
0
n=10
–
–
100
385.73
670.92
0
3916.05
635.39
0
209.96
0
n=11
–
–
100
799.51
2557.1
0
9740.77
2399.79
0
484.85
0
n=12
–
–
100
1507.14
9420.3
0
20671.8
8025.94
0
1884.41
0
n=13
–
–
100
3377.62
29524.7
0
52226
25953.6
0
2804.59
0
n=14
–
–
100
7322.17
110221
0
152133
102022
0
8191.31
0
n=15
–
–
100
17920.8
357324
5
187162
193285
18
18217.55
0
23
ランダムグラフ
ランダムグラフに対する実験結果を表 5.2 にまとめる．
表からわかるように，どのアルゴリズムの場合においても同じ辺密度であるセミクリーク
グラフより実行速度が遅くなっている．特に，片面 14 頂点を超えると下界によるアルゴ
リズムでは解を導き出すことができないことがわかる．
表 5.2
ランダムグラフに対する実行結果
Path
頂点数
再帰の深さ
OSCM
Cross
IP
速度 [ms]
失敗数
再帰の深さ
速度 [ms]
失敗数
再帰の深さ
速度 [ms]
失敗数
速度 [ms]
失敗数
n=6
974719
304.28
0
63.51
2.85
0
230.09
4.24
0
112.9
0
n=7
54424836
21369.9
0
166.4
20.5
0
570.5
31.2
0
185.9
0
n=8
–
–
100
533.01
98.37
0
2167.89
261.44
0
227.91
0
n=9
–
–
100
2614.86
653.36
0
13378.2
2564.49
0
302.09
0
n=10
–
–
100
9093.38
2996.35
0
56450.3
15537.2
0
512.98
0
n=11
–
–
100
45191.8
17785.2
0
408694
152972
0
1489.79
0
n=12
–
–
100
256339
153300
0
561116
344079
79
10189.69
0
n=13
–
–
100
301082
497733
95
–
–
100
126994
9
n=14
–
–
100
–
–
100
–
–
100
144991
4
n=15
–
–
100
–
–
100
–
–
100
–
100
速度 [ms]
失敗数
速度 [ms]
失敗数
非常に辺密度の低いグラフ
辺密度の低いグラフに対する実験結果を表 5.3 にまとめる．
このようなグラフの場合，IP が圧倒的に高速な動作をしていることがわかる．また，速
度，再帰の深さ共に OSCM の方が良い結果となった．
表 5.3
非常に辺密度の低いグラフに対する実行結果
Path
頂点数
再帰の深さ
OSCM
Cross
速度 [ms]
失敗数
再帰の深さ
速度 [ms]
失敗数
再帰の深さ
IP
n=6
292246
72.39
0
28.93
3.72
0
152.48
3.1
0
21.72
0
n=7
14398161
4237.3
0
52.5
8.5
0
299.6
12.7
0
33.0
0
n=8
985450794
331828
18
111.22
26.39
0
838.66
61.85
0
46.21
0
n=9
–
–
100
210.43
86.44
0
2349.44
272.92
0
65.42
0
n=10
–
–
100
483.46
291
0
7243.39
1328.22
0
89.48
0
n=11
–
–
100
1152.44
982.38
0
23409.8
6160.19
0
144.78
0
n=12
–
–
100
4094.45
3611.2
0
89233.2
34179.4
0
188.91
0
n=13
–
–
100
12327.6
13310.8
0
298453
155621
9
215.71
0
n=14
–
–
100
56997.4
80626
4
239462
249634
61
578.87
0
n=15
–
–
100
170542
149033
5
639808
253157
86
1164.37
0
24
非常に辺密度の高いグラフ
辺密度の高いグラフに対する実験結果を表 5.4 にまとめる．
このようなグラフにおいては，他のグラフでは非常に高速に動作していた IP が多くの
ケースで解を見つけることができなくなっていることがわかる．また，OSCM と Cross
に関しては，OSCM の方が優れた結果を出していることがわかる．
表 5.4
非常に辺密度の高いグラフに対する実行結果
Path
頂点数
OSCM
Cross
再帰の深さ
速度 [ms]
失敗数
再帰の深さ
速度 [ms]
失敗数
再帰の深さ
n=6
1415743
1028.91
0
54.49
7.65
0
n=7
69103581
71500.8
0
183.2
34
0
n=8
–
–
100
713.45
195.21
n=9
–
–
100
4513.79
n=10
–
–
100
n=11
–
–
100
n=12
–
–
n=13
–
n=14
n=15
IP
速度 [ms]
失敗数
速度 [ms]
失敗数
228.99
8.08
0
510.08
0
1346.7
67.34
0
2980.5
0
0
11836.3
834.1
0
85226.3
3
3415.44
0
246164
26651.5
0
197144
75
19847.3
2058.32
0
628316
27743.8
4
–
100
83743.9
11724.9
0
1599277
117560
14
–
100
100
353146
75893.6
0
2347243
326247
72
–
100
–
100
541813
373047
85
–
–
100
–
100
–
–
100
–
–
100
–
–
100
–
100
–
–
100
–
–
100
–
–
100
–
100
これらの結果から次のことがわかる．
• Path のアルゴリズムは辺密度が低い場合では動作するが辺密度が高くなることで
性能が落ちる
• セミクリークグラフにおいては Cross の方が OSCM よりも平均実行速度が速い
が，失敗件数が多い
• その他のグラフにおいては OSCM の方が Cross よりも平均実行速度が速い
• 密で無いグラフにおいて IP は最速であり，他のアルゴリズムに比べ非常に高速に
動作している
• 密なグラフにおいて IP は非常に低速となる
結果については次節で考察する．
5.2.2 考察
実験結果から，Path は辺密度に大きく依存して実行速度が変化する．これは，辺素な
パスを最短経路を利用して求めているところにあると考えられる．ダイクストラのアルゴ
リズムは辺の多さに強く依存した実行時間となる．このアルゴリズムにおいては各再帰の
25
度に最短パスを求め下界を利用しているが，辺密度が高い場合，パスとなり得る辺数が多
くなるため実行速度が遅くなると考えられる
次に，セミクリークグラフにおける実行時間であるが，Cross の場合，OSCM に比べ探
索の早い（再帰の浅い）段階で，大きく交差するような辺を発見することができるため，
高速に動作したのであると考えられる．しかしながらその他のテストケースにおいては，
動的計画法によって片面の最適順序を高速に計算できる OSCM の方がより高速に動作す
ることになったのであると考えられる．
IP の実行速度についてであるが，辺密度が高くないという条件において，IP は最速と
なった．これは，その他のアルゴリズムでは基本的にバックトラックによって頂点順序を
決定しているため，L 層（L は T か B ）の任意の頂点対 {a, b} に対し，探索の都度 a <L b
か a >L b による割り当てを行なう点に原因があると考えられる．IP の場合整数計画法を
解くために利用する変数 δ, β が，同一層内における 2 頂点対の配置情報を変数として保持
しているため，値の確定した変数の情報を一度も解放せずに利用できる事が高速化の要因
となっている考えられる．また，CPLEX の場合は，実行時に内部で非常に強力な切除平
面法アルゴリズムを利用している事が，更なる高速化につながったのではないかと推測で
きる．ただし，辺密度が多くなる場合 4.3 においては，膨大な量の変数を保持しなければ
ならず，またそれに伴い莫大な解空間での実行可能解の探索を行なう必要が出るため，実
行速度が低下したのであると考えられる．
5.3 実験 2
実験 1 から，CPLEX により多くのテストケース対し，整数計画法が非常に高速に動作
するということがわかったため，CPLEX を利用した更なる高速な解法について考える．
更なる高速化を目指すにあたり，組み合わせ的に得られる下界に対し，整数緩和を行なっ
た LP から得られる下界の性能について比較することを目的とする．下界の性能比較にお
いては，単純にアルゴリズムを走らせ，解を得られるまでの実行速度を比較するのではな
く，それぞれの下界によって得られた値から性能を比較するものとする．
具体的には，線形計画法の目的関数 4.3 に対し，次のような式を加えた整数計画法を解
くことで得られる解と，Cross における K2,2 から導かれる値を比較する．これにより，
LP から得られる下界の性能と，Cross に用いられる下界の精度を調べることが出来ると
思われる．
ただし，目的関数が式 4.3 のまま整数制約を緩和してしまうと，全ての変数に対し 0.5
を割り当てることで実行解が 0 に収束してしまう．これを避けるためには，切除平面法と
なり得る制約式を新たに追加する方法が挙げられる．
5.3.1 追加した制約式
制約式の追加に際し，次のような観察を行なう．
L
• 任意の層 L における任意の頂点対 {a, b} に対する変数 δa,b
は Cross における未確
26
定の頂点対以外の情報を織り込める
• 目的関数 4.3 における −2βk,l,i,j は，式全体から交差を生じえない辺対を取り除い
ている
上記を踏まえた上で元の制約式に対し，次の式を追加する．
nB ′ −1 nB ′
(
∑
i=1
∑
∑
∑
′
′
T
B
δkl
+ δij
− 2βklij ) ≥ cr
(5.1)
j=i+1 k∈N (i)⊆T ′ (l∈N (j)\k)⊆T ′
5.1 における T ′ , B ′ とは，それぞれ層となる頂点集合 T, B から誘導される部分グラフ
であり cr とは，T ′ , B ′ によって作られる部分グラフの最小交差数である．この式を追加
することで，入力となるグラフ G のある部分グラフ部分 G′ に含まれる任意の 4 頂点対は
cr 以上の交差を生じる事になるため，組み合わせ的に未探索な頂点対へ制約を加えるこ
とが期待される．
5.3.2 実験方法
実験 1 で利用した全てのテストケースに対し，5.1 を追加した LP 解と，K2,2 によ
る値を比較する．5.1 については，入力となる 2 部グラフ G の部分グラフ G′ に対し，
|T ′ | = |B ′ | = 2 (T ′ ⊆ G′ , B ′ ⊆ G′ ) とした場合について性能を比較する．
5.3.3 実験結果
|T ′ | = |B ′ | = 2 と置いた場合，グラフの特性に関わらず 4000 件全ての入力において，
LP の解は K2,2 から得られる解と同じ値となった．
5.3.4 考察
|T ′ | = |B ′ | = 2 の場合，G′ に選ばれるのは各層 2 頂点ずつであり，cr(G′ ) の最適解自
体が K2,2 と一致することになるため，このような結果になったと考えられる．
27
第6章
まとめ
本論文では，グラフの交差数最小 2 層描画問題に対するいくつかの分枝限定アルゴリズ
ムを提案し，整数計画法ソルバーとの速度比較から下界の性能について考察した．実験の
結果から，辺密度の高いケースにおいては有用な下界があるものの，多くのケースにおい
てはバックトラックによる探索を整数計画法による解法よりも高速に動作させることが困
難であるということを示した．
また，その後の実験により，組み合わせ的に得られる値を用いた下界が切除平面法の制
約となり得ることから，当該問題に対する整数計画法の更なる高速化ができる可能性を示
した．
現状の課題としては，今回行なった実験では下界の性能，および実行時間について画期
的な高速化ができなかった点である．
カット自体の性能の向上は複雑であり，弱い制約条件では解が 0 に収束してしまい，逆
に強すぎる制約条件では最適解へ収束することができなくなってしまう．これらを踏まえ
た上で今後の展望としては，最適解を満たしながらも，より強力なカットとなり得る制約
式を考案し，切除平面法によってより高速に TLCM を解く手法について考えていくこと
である．今回の実験から，LP によって組み合わせ最適化アルゴリズムと同等の性能を持
つ優れた下界が導き出せることが示せたので，それを組み合わせることで更なる高速化が
期待できる．
28
謝辞
本研究において，新たなアルゴリズムの設計から，実験方法，研究の方針決定など多く
のことで大変熱心にご指導いただきました，指導教員の玉木久夫教授に心より感謝申し上
げます．また，昨年度卒業したにも関わらず，メール等で何度も助言やアイデア出しをし
ていただいた小林靖明先輩にも，深く感謝致します．そして，別の研究をしているにもか
かわらず本研究の議論に積極的に参加し，本論文で用いられた下界の内，LP へ展開する
うえで非常に有用なヒントとなった Cross と，OSCM のアルゴリズム設計をしてくれた
同研究室の小室慶太君と，修論を書き上げる際に何度か手を貸してくれた橘内謙太君にも
感謝します．
最後に，日常の議論において多くの知識や示唆を頂き，また普段の生活において大変楽
しい時間を過ごさせてくれた計算理論研究室の皆様に感謝します．
29
参考文献
[1] A. Hussain , A. Abdullah, A new biclustering technique based on crossing minimization, Neurocomputing,69(16),Elsevier,pp.1882–1896,2006
[2] Y. Kobayashi, H. Maruta, Y. Nakae, and H. Tamaki, A Linear Edge Kernel
for Two-Layer Crossing Minimization., Computing and Combinatorics.,Springer
Berlin Heidelberg,pp.458–468,2013
[3] L. Zheng and C. Buchheim, A new exact algorithm for the two-sided crossing
minimization problem., Proceedings of the 1st International Conference on Combinatorial Optimization and Applications, COCOA2007, pp.301–310, 2007.
[4] IBM ILOG User’s Manual for CPLEX, International Business Machines Corporation 46(53), pp.157,2009.
[5] F. Shahrokhi, et al., On bipartite drawings and the linear arrangement problem.,
SIAM Journal on Computing 30(6),pp.1773–1789, 2001.
[6] T. Lengauer, Combinatorial algorithms for integrated circuit layout., John Wiley
and Sons, Inc., 1990.
[7] G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph drawing: Algorithms for drawing graphs: an annotated bibliography., Computational Geometry
4(5) ,pp.235-282.,1994
[8] M. S. Waterman and J. R. Griggs, Interval graphs and maps of DNA., Bulletin
of Mathematical Biology, 48(2), pp.189–195, 1986.
[9] T. D. LaToza and B. A. Myers, Visualizing call graphs., Visual Languages and
Human-Centric Computing (VL/HCC),IEEE Symposium on. IEEE,2011.
[10] Dı́az, Josep, Jordi Petit, and Maria Serna., A survey of graph layout problems.,
ACM Computing Surveys (CSUR),34(3),pp.313–356,2002
[11] O. Bastert, and M. Christian., Layered drawings of digraphs., Drawing graphs.,
Springer Berlin Heidelberg, pp.87–120,2001.
[12] H. Purchase, Which aesthetic has the greatest eﬀect on human understanding?.
Graph Drawing. Springer Berlin Heidelberg, 1997.
[13] M. R. Garey and D. S. Johnson., Crossing number is NP-complete., SIAM Journal on Algebraic Discrete Methods 4(3),pp.312–316,1983.
[14] K. Sugiyama, T. Shojiro, and T. Mitsuhiko. em Methods for visual understand-
30
ing of hierarchical system structures. IEEE Transactions on Systems, Man and
Cybernetics, 11(2),pp.109–125,1981.
[15] V. Dujmović, and S. Whitesides., An eﬃcient ﬁxed parameter tractable algorithm
for 1-sided crossing minimization., Algorithmica 40(1),pp.15–31, 2004.
[16] V. Dujmović, S. Whitesides and M. Kitching, On the parameterized complexity
of layered graph drawing., Algorithmica 52(2),pp.267–292,2008
[17] Y. Kobayashi and H. Tamaki, A fast and simple subexponential ﬁxed parameter
algorithm for one-sided crossing minimization., Proceedings of the 20th Annual
European Symposium on Algorithms, ESA 2012, pp.683–694, 2012.
[18] H. Fernau, F. V. Fomin, D. Lokshtanov, M. Mnich,
Ranking and
drawing in subexponential time. Combinatorial Algorithms., Springer Berlin
Heidelberg,pp.337–348, 2011.
[19] V. Dujmović, H. Fernau, and M. Kaufmann.,
Fixed parameter algorithms
for one-sided crossing minimization revisited. Journal of Discrete Algorithms
,6(2),pp.313–323,2008
[20] P. Eades and S.Whitesides., Drawing graphs in two layers., Theoretical Computer
Science ,131(2) pp.361–374,1994.
[21] V. Dujmovic, et al.
A ﬁxed-parameter approach to 2-layer planarization.,
Algorithmica,45(2),pp.159–182,2006.
[22] M. Suderman. Layered graph drawing., PhD thesis, School of Computer Science
McGill University, 2005.
[23] V. Valls, R. Martı́, and P. Lino. , A branch and bound algorithm for minimizing
the number of crossing arcs in bipartite graphs., European journal of operational
research,90(2) ,pp.303–319,1996.
[24] R. Bellman. Dynamic programming treatment of the travelling salesman problem.,
Journal of the ACM (JACM) 9(1),pp. 61–63,1962.
[25] M. Held, and R. M. Karp, A dynamic programming approach to sequencing
problems. , Journal of the Society for Industrial & Applied Mathematics,10(1) ,
pp.196–210, 1962.
[26] R. G. Downey and M. R. Fellows, Parameterized complexity. , Vol.3., Heidelberg,springer, 1999.
[27] 中江勇介, 2 部グラフの 2 階層描画の辺交差数最小化, Master’s thesis, 明治大学大
学院理工学研究科, 2012.
31

Download Report