数理解析研究所講究録
第 1799 巻 2012 年 163-166

163

2011 年度冬の LA シンポジウム [S4]距離遺伝 2 部グラフ上のハミルトン閉路アルゴリズム

An algorithm for the Hamiltonian circuit problem
on bipartite distance-hereditary graphs
高須賀将秀 *

1

平田 富夫 *

はじめに距離遺伝グラフに対し，$O(|V|+|E|)$ のアルゴリズ
ムが報告されている [5][6] が，本論分のアルゴリズムはハミルトン閉路問題は有名な NP 完全問題であるが，グラフを制限することで多項式時間で解ける場合がある．本研究では距離遺伝 2 部グラフに制限することで多項式時間でハミルトン閉路を発見するアルゴリズムいと考えられる．

を提案する．このグラフに対しては既に多項式時間の2アルゴリズムが提案されているが [4], それとは違ったアプローチのアルゴリズムを提案する．提案するアルゴリズムはよりシンプルでグラフクラスの拡張や改良がしやすいと考えられる．
$G$ のすべての頂点を無向グラフ $G=(V, E)$ に対し，ちょうど 1 回通る閉路をハミルトン閉路と呼ぶ．ハミルトン閉路問題とは，グラフ $G=(V, E)$ を入力とし，にハミルトン閉路が存在するかどうかを判定する問

これらより単純で実装やグラフクラスの拡張がしやす

縮小グラフ

をそれBDHG $G=(V^{+}, V^{-}, E)$ において，ぞれグループ (同値類) に分け，そのグループを新たな$V^{+},$ $V^{-}$

頂点とした縮小グラフ$G^{r}$を提案する．

まず，グループの分け方について述べる．$R$ は頂点集合$V$上の関係で，$v_{i}R_{v_{j}}$は $N(v_{i})=N(v_{j})$ であるこ

$V$ のグループ分けとは $R$ による $V$ のとを表すとする．

$G$

同値分割のことである．この同値類

題である．

次のようにしてグラフ $G^{r}=(V^{r}, E^{r})$ を構成する．

$n$頂点の無向グラフに対するハミルトン閉路に対し各種の指数時間アルゴリズムが提案されているが，最近モンテカルロ法を使った $O(1.657^{n})$ 時間のアルゴリズムが報告された [2]. また，2 部グラフに対しては，$O(1.414^{n})$ 時間のアルゴリズムが報告されている．

グラフを制限することで，この問題を多項式時間で解くことができる場合がある．これまでの研究で，プト$\gamma_{i}(1\leq i\leq t)$$V^{r}$の各頂点は各同値類 に対応し， において 2 つの同の頂点間に辺を値類間に辺があるとき，対応する$G$$\gamma_{i}$$G^{r}$

引く．の次に， : $Varrow V^{r}$ を の頂点を縮小グラフがグループ頂点に写像する関数とする．っまり，$G$$\gamma$$G^{r}$$v$に属しているとき，$\gamma(v)=\gamma_{i}$ループ$\gamma_{i}$である．また，$||\gamma_{i}||$縮小グラフは相互に変換可能である．

計算時間のアルゴリズムが報告されている [8]. プトレ
マイックグラフとはコーダル (chordal) でかつ距離遺伝 (distance hereditary) なグラフである．また，2 部グ21の計算時間のアルゴリズムが与えられている [4]. 本論
文では $O(|V|^{2})$ のアルゴリズムを与える．なお，コーダルな 2 部グラフに対してはこの問題は NP 完全である [3].
*名古屋大学大学院情報科学研究科$\gamma_{i}$をグに属している頂点数と定義する．BDHG とレマイックグラフ (Ptolemaic graph) に対し $O(|V|)$ のラフでかつ距離遺伝なグラフに対し $O(|V|(|V|+|E|))$から縮小グラフに関する性質

ここでは，縮小グラフに関する重要な性質について述べる．

命題 21. $[\eta c$ を少なくとも 1 本以上の辺が存在する

BDHG とすると，その縮小グラフ$G^{r}$には次数 1 の頂点が少なくとも 1 つ存在する．

証明．省略口

164
命題 22. [7]を縮小グラフ上の次数 1 の任意の$G$頂点とする． を対応する 上のグループ に含まれ$G^{r}$$\gamma_{i}$$y$$\gamma_{i}$が$x\in N(y)$ とする．このとき，グラフる頂点とし，である．
であるならばもBDHG
BDHG
$G$

$G\backslash \{x, y\}$証明．省略$n$に関する帰納法で証明する．

まず，グラフが 4 頂点のとき，拡張条件が成立するので， は完全 2 部クリークとなり，ハミルトン閉路は$G_{2n}$存在する．

において定理の命題が成立すると仮定して，においてもこの命題が成立することを示す．にお$G_{2(n+1)}$ は BDHG なので命題 21 よりいて次数 1 の頂点 : が存在する．また，補題 32 よ$G_{2}n$$G_{2(n+1)}$

証明．省略$G_{2(n+1)}^{r}$$\gamma$3

り，$G_{2(n+1)}$

拡張条件についてから $y\in\gamma_{:},x\in N(y)$ を取り除いた$G_{2(n+1)\backslash \{x,y\}}$頂点の 2 部グラフで，ハミルトン閉路を持つとする．明らかに $|V^{+}|=|V^{-}|=n$ で$X$ を $V^{+}(V^{-})$ の任意の頂点集合とする $(|X|<$ある．
$G=(V^{+}, V^{-}, E)$ は $2n$$n)$.

$X$において拡張条件が成立する．帰納法の仮定より $G_{2(n+1)\backslash \{x,y\}}$ においてハミルトン閉路が$G_{2(n+1)}$ においても存在する．よって，補題 31 より，ハミルトン閉路が存在する口の隣接頂点の集合を $N(X)= \bigcup_{v\in X}N(v)$ と表$|X|<|N(X)|$ が成り立っている．なぜす．このとき，$G$なら，がハミルトン閉路を持つからである．次の条

件を $G$ の拡張条件と呼ぶ．

4

アルゴリズム
$G=(V^{+}, V^{-}, E)$

を $2n$ 頂点の BDHG とする．た$|V^{+}|=|V^{-}|=n$ である．本節では
だし，拡張条件 : $\forall x|X|<n\Rightarrow|X|<|N(X)|$$G$にハミルトン閉路があるか否かを判定するアルゴリズムを提案

この拡張条件は， にハミルトン閉路が存在するための必要条件であるが， が一般的な 2 部グラフの場合十分条件ではない．ここでは， が BDHG の場合，
$G$

$G$

$G$

この条件が $G$ にハミルトン閉路が存在するための十分条件であることを示す．

する．

既存アルゴリズム [4] はグラフの生成構造を表すOVE 列を用いるため，計算時間が増大する．我々は，異なるるアプローチによるアルゴリズムを提案する．そというよりシンプル

れは BDHG $G$ を縮小グラフ

補題 3.1. [7] グラフ $G$ は BDHG であるとする．: を$G^{r}$なグラフに置き換え，そのグラフ上でハミルトン閉路$\gamma$$G$ 上の対応縮小グラフ上の次数 1 の頂点とする．
するグループ において任意に 1 個頂点を選ぶ．それ$G^{r}$を探索していく手法である．このアルゴリズムは縮小グラフとこれまでに証明した補題を用いてハミルトン$\gamma_{1}$を$y$$x\in N(y)$ とする． にハミルトン閉路が存とし，$G$在するとき，そしてそのときのみ$G\backslash \{x,y\}$にハミルト閉路の有無を判定し，縮小グラフのサイズを再帰的に小さくしていく．

ン閉路が存在する．

41
証明．省略口補題 32. [7] $2n$ 頂点のグラフ $G$ は BDHG であるとする．このとき， において拡張条件が成立するなら$G$ば$G\backslash \{x,y\}$においても拡張条件が成立する．

証明．省略口定理 3.3. [7] グラフ $G_{2n}=(V^{+}, V^{-},E)$ を $2n$ 頂点の$IV^{+}|=|V^{-}|=n$ であるとする．このとき，
BDHG で，アルゴリズムの詳細は次のように実装される．まず， 上の頂点の次数が 1 である頂点をリスト Ll に記憶しておく．ま$G^{r}$$G^{r}$

上のに属している
た， 上の各頂点点の個数をで表す． 上の頂点 の隣接頂点の$G^{f}$$||\gamma_{1}||$

リストを NL$\gamma_{l}$として記憶, 各頂点の次数をの中身は頂点番号の小さしておく．このとき，$\deg(\gamma_{l})$$(\gamma_{i})$$NL(\gamma_{i})$い順にソートされているものとする．
$G$
アルゴリズムの詳細は次のとおりである．まず，からを作る． の中から任意に 1 頂点を選び，そ$G^{r}$

において拡張条件が成立するならばハミルトン閉路が存在する．

$G$

$G$

$\gamma_{i}(1\leq i\leq t)$$G^{r}$の頂点を$L_{1}$$\gamma_{p}$とする． の隣接頂点は点を$\gamma_{p}$$\gamma_{q}$とする．

165
ならば，‘ハミルトン閉路は存在しないと出力する (定理 33). そうでないならば， から頂点の更新 を行う．アルゴリズムを取り除き，‘”$\Vert\gamma_{p}\Vert\geq\Vert\gamma_{q}||$$G^{r}$$Algorithm1l:BDHGG$$G^{r}$

から対応する縮/」 グラフ$\backslash$”$G^{r}$を作る$\gamma_{p}$は上の操作を繰り返す (Algorithml).
$G^{r}$の更新” は次のとおりである．補題 31 より，グループ物の頂点がなくなるまで頂点 $x,y$ の削除を繰り返す． の頂点がなくなるので， では頂点が削除される．また， の値をだけ減少し，頂点の次数の値を 1 だけ減少する．ここで，$G^{r}$$\gamma_{p}$の次数が 1 になるのであればをリスト$\gamma_{q}$$G^{r}$$\gamma_{i}$ストとする
4:を $G$ 上のグループ$\Vert\gamma_{i}\Vert$に属している頂点の個$\gamma_{i}$数とするの処理を行っている．

その後， 上の頂点 の隣接頂点集合 NL との隣接頂点集合 NLが一致するような頂点 を見つけ出す．そのようなグループ と は 1 つのグルー$G^{r}$$(\gamma_{q}$$\gamma_{q}$$(\gamma_{k})$5: NLを$(\gamma_{i})$$G^{r}$

上の頂点$\gamma_{i}$の隣接頂点のリストとする$L_{1}$に加える．Algorithm2 の 1 行目から 6 行目がこの削除

6: deg( のを頂点$\gamma$$\gamma_{i}$の次数とする

7: if $|V^{r}|=2$ thenハミルトン閉路が存在する” と出力する“

8.

$\gamma_{k}$9: end if$\gamma_{k}$$\gamma_{k}$I $V^{r}|>2$ do

10: while$\gamma_{q}$プにまとめられるので，それらのグループに属している頂点のリストを足し合わせる．そうすると$G^{r}$においの隣接頂点は次数が 1 減少する．もしの値が 1 となったら伽を に加える．Algorithm2 のては$L(\gamma_{i})$$||\gamma_{p}||$$\deg(\gamma_{q})$$\gamma_{q}$$\gamma_{q}$3:上の次数 1 の頂点のリストとするを $G$ 上のグループに属している頂点のリを$\gamma_{p}$$||\gamma_{q}\Vert$

もし2:$L_{1}$$\deg(\gamma_{k})$$\gamma_{k}$$L_{1}$

7 行目から 16 行目がこの処理を行っている．
このアルゴリズムは縮小グラフを元に動作している
ため，全体の計算量は縮小グラフの頂点数 に依存する．
アルゴリズム 1 の 10 行目の while は縮小グラフの更新回数分，つまり高々 回行われる．アルゴリズム 2 の上の7 行目のの隣接頂点集合が一致する頂点を
$t$

$t$

11:

$\deg(\gamma_{p})=1$12:$r_{q}$

if

13:

を$\gamma_{p}$を選択する

then“ハミルトン閉路は存在しない” と出力する

else

15:

16:
17:

である頂点に隣接する頂点とする$||\gamma_{p}\Vert\geq\Vert\gamma_{q}||$

14:

ls:

$r_{p}$$G^{r}$の更新 [Algorithm2]

end ifend while

19:‘ハミルトン閉路が存在する” と出力する$G^{r}$$\gamma_{q}$となる範囲で を探探す．これは，せばよいが，1 頂点の比較で一致しているか $O(t)$ の計$k$$\deg(\gamma_{q})=\deg(\gamma_{k})$

算時間がかかるため，Searchk such NL$(\gamma_{k})=NL(\gamma_{q})$は $O(t^{2})$ かかる．の 更新”$A1gorithm2G^{r}1:\Vert\gamma_{q}\Vert=\Vert\gamma_{q}\Vert-\Vert$
$|$

2: NL

$(\gamma_{q}=NL(\gamma_{q})\backslash \{\gamma_{p}\}$3: $\deg(\gamma_{q})=\deg(\gamma_{q})-1$
4: if $\deg(\gamma_{q})=1$ then42

5:

アルゴリズムの実装

上で述べたアルゴリズムでは縮小グラフ

6: end if$G^{r}$の隣接リスト NL $(\gamma_{i})(1\leq i\leq t)$ を用いてるため，全体の計算時間は $O(t^{3})$ であった．各隣接リストの中身はソートされているので，これら 個の隣接リストからトライを構成すれば Algorithm2 の 7 行目は $O(t)$ の時間で実$t$行できる．

図 1 左のような縮小グラフに対するトライ木を同図1 右に示した．縮小グラフの頂点とトライ木の四角で囲まれた頂点は対応している．トライ木において，根から四角で囲まれた頂点 へ至る路をたどることでNL( のが得られる．なお，この四角で囲まれた頂点$\gamma_{i}$$\gamma$$L_{1}:=L_{1}\cup\{\gamma_{q}\}$$\gamma_{i}$7: Search $k$ such that NL $(\gamma_{k})=NL(\gamma_{q})$$8$: if such

9:10;

$k$

exists then$||\gamma_{k}||=\Vert\gamma_{k}\Vert+||\gamma_{q}||$

FOR$x\in \mathfrak{W}(\gamma_{k})$11:$\deg(z)=\deg(z)-1$

12:

if $\deg(z)=1$13:$L_{1}=L_{1}\cup\{z\}$end ifend FOR15:
16: end if
14:

166
へのポインタを配列 に記憶しておくことで，トライ内の (四角で囲まれた) 頂点へのアクセスが定数時間で$n$できるようにしておく．

縮小グラフの更新では頂点$i\leq h)$$\gamma:(1\leq i\leq t)$と辺亀 $(1\leq$の削除が行われる．これをトライ上で実行するが，縮小グラフの各辺についてトライ上での更新はアルゴリズム全体を通して 1 回ずつしか行われない．そのため，アルゴリズム全体の計算量は $O(t+h)$ になる．
よりかなり小さくなるこ
グラフが密の場合， は$|V|$$t$とが期待でき，既存のアルゴリズムより効率が向上す$t=O(|V|)$ のときは，提案アルゴリズムの計算量
る．

は $O(|V|+|E|)$ である．

natorial Theory, pp. 182-208, 1984.
[2] Andreas B\"orklund. Determinant Sums for Undirected Hamiltonicity. Foundations of Computer
Science (FOCS), pp. 173 –182, 2010.
[3] Haiko M\"uller. Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics, Vol. 156,
pp. 291-298, 1996.

[4] Haiko Muller and Falk Nicolai. Polynomial timealgorithms for Hamiltonian problems on bipartite
distance-hereditary graphs. Information Prvcessing Letters 46, pp. 225-230, 1993.

[5] Maw-Shang Chang Ruo-Wei Hung.
Lineartime algorithm for the Hamiltonian problems
on distance-hereditary graphs. Theoretical Com, 2005.
puter Science, Vol. 341, pp.

$@_{\overline{\backslash }}..@$$411\triangleleft 40$$Nl(r|)=h_{2}.\tau s1$

O

国日

$15|$
$\kappa\iota_{\mathscr{T}_{1u1}^{hd}}N\iota(\gamma_{3})(2)$$Nl<’\prime\prime)=t’\prime 1\cdot\gamma s’d$日$\kappa\iota t\approx)=|u^{\ell}r|$$n\iota(\alpha)=\dagger d$[6] Tsan-Sheg Hsu Ming-Tat Ko Sun-Yuan Hsieh,
Chin-Wen Ho. The Hamiltonian problem on
市就 anoe hereditary graphs.
DISCRETE APPLIED MATHEMATICS, pp. 508-524, 2006.

[7] Masahide Takasuka and Tomio Hirata. 距離遺伝
図 1: トライ木

5

結論

本研究では BDHG に対するハミルトン閉路問題のアルゴリズムを提案した．縮小グラフと拡張条件という新しい概念を用いたことが既存研究と異なる点である．
既存アルゴリズムの計算時間は $O(|V|(|V|+|E|))$ で辺の数が大きくなると計算量が大きくなる．つまり，FT 操作が多い BDHG に対しては計算量が大きくなる．しかし，本論文で提案するアルゴリズムは計算量が縮小グラフの頂点数に依存するため，そのような問題に対して高速に問題を解くことができる．

参考文献[1] Hans-J\"urgen Bandelt and Henry Martyn Mulder.
Distance-Hereditary Graphs. Joumal of Combi-2 部グラフ上のハミルトン閉路アルゴリズム．2012.

[8] TAKAHARA Yoshiriro, TERAMOTO sachio,and UEHARA Ryuhei. Longest Path Problem on
Ptolemaic Graphs. JAIST Repository, pp. 170177, 2008.