数理解析研究所講究録
第 1554 巻 2007 年 109-116

109

Ptolemaic Graph 上の最長路問題に関する研究
高原祥浩, 寺本幸生, 上原隆平
Yoshihiro Takahara, Sachio Teramoto, Ryuhei Uehara
北陸先端科学技術大学院大学情報科学研究科
Japan Advanced Institute of Science and Technology (JAIST)

概要

inar Ttee と呼ばれる木表現を持ち、 この性質を利用してハミルトン閉路問題が線形時間で解けることが示されている。 本論文ではこの結果を拡張し| Ptolemaic Graph 上のハミルトン路問題最長閉路問題・最長路問題を多項式時間で解くアルゴリズムを提案する。

決の糸口となる。
上原宇野により、木表現を利用した動的計画法で Ptolemaic Graph 上のハミルトン閉路問題が線形時間で解けることが示されている[7]。
本研究では、 Ptolemaic Graph の木表現が持っ性質と、 それを使ったハミルトン (閉) 路
問題の解法を拡張し、 最長 (閉) 路問題を効率よく解くことを目的とする。
[1] の方法では Clique Laminar $hee$ と比較して弱いグラフ構造を用いており、最長 (閉) 路問題への拡張は困難であると考えられる。 本

1

研究では、 まず Chque Laminar Lee を用いた
ハミルトン閉路問題の解法を示し、 ハミルトン路問題と最長 (閉) 路問題の解決に拡張する。

Ptolemaic Graph とは、 Ptolemaic inequality を満たし、 Chordal Graph と Distance
Hereditary Graph の共通部分となるグラフクラスである Q Ptolemalc Graph は Clique Lam-

研究の背景と目的

現在、 いくっかのグラフクラスにおいては、
ハミルトン (閉) 路問題や最長 (閉) 路問題が多項式時間で計算可能かどうか証明されていな
い。 特に最長路問題に関しては殆ど研究が行われておらず、効率的に解けるグラフクラスは限られている。

Graph とは、 Ptolemaic inequality を満たし、 Chordal Graph と Distance
Hereditary Graph の共通部分となるグラフク$Ptolem\dot{u}c$

ラスである。 Ptolemaic Graph 上でハミルト
ン (閉) 路を求める線形時間アルゴリズムは存在するが $[1, 7]$ 、最長 (閉) 路問題については効率的な解法が知られていない。
Ptolemaic Graph に関する重要な特徴づけとして、上原宇野による包含関係に基づいた木構造による表現が挙げられる [7]。いくつかの木表現をもつグラフクラスに対しては、動的計画法を使うことで最長路を多項式時間で見つけることが出来る。そのため、 Clique Laminarlee と呼ばれるこの木表現は、 最長路問題解

ハミルトン路問題は全ての頂点を接続する必要があるという点で、 ハミルトン閉路問題と同質である。 しかしパスの端点を計算する過程が必要となり、ハミルトン閉路問題よりも複雑である。
最長閉路は最長という条件のためハミルト
ン閉路とは異なり、 どんなグラフ上にも存在する。全ての頂点を使用する必要が無く、頂点の取捨選択が要求される点がハミルトン問題と比較して困難である。
Ptolemaic Graph における最長路問題は、ハミルトン路問題と最長閉路問題の性質を併せ持っ問題であり、パスを求める手続きと、頂点を選別する手続きを組み合わせる必要がある。

2

Ptolemaic Graph

2.1

定畿

Ptolemaic

Graph とは、 任意の 4 頂
Ptolemaic inequal-

点 $x,y,z,w$ に対して$\backslash$

110
ity

$d(x, z)d(y, w)+$$d(x, w)d(y, z)$ を満たすグラフであり、 平
面幾何的な性質をもつ。 図 1 左は Ptolemaic
Graph の例である。
$d(x, y)d(z, w)$$\leq$$L(G)$ の要素は $G$ のセパレータとなる (補題 1)。

またノード間の包含関係は層 (laminar) 構造をもつことから、 この木表現は Clique Laminar
Tree と呼ばれる。 $arrow T(C(G))$ の有向辺を無向辺で置き換えたものを $T(C(G))$ と表記する。
Clique LamInar $Ree$ [こついて、 以下の定理が存在する。
定理 2. [7] $G=(V, E)$ が Ptolemaic であるのは、 $T(C(G))$ が木であるとき、 かつそのときに限る

図 1: Ptolemaic Graph とその木表現の例与えられた Ptolemaic Graph に対し、 Clique

Laminar Tree は線形時間で構築できること
Ptolemaic Graph に関して、 以下の定理が存在する。
定理 1. [5] 次の 3 つの命題は等しい :(1) $G$
は Ptolemaic Graph; (2) $G$ は d-stanoe hered-itary1 かつ $\bm{i}orda1^{2};(3)$ 空でない共通部分を持つ任意の異なる極大クリークとて、 $P\cap Q$ はを分割する。
$P$$P\backslash Q$と $Q$ に対し

$Q\backslash P$

が示されている。 図 1 左は図右の Ptolemaic
Graph を木表現に変換したものである。 極大クリーク $M(G)$ が 2 重のノード、 それらの共通部分 $L(G)$ が通常のノードに対応している。

本稿では Ptolemaic Graph の構成要素である
頂点 に対し ‘ Clique Lminar Ree 上の頂点
集合 $C(G)$ に含まれる要素 ( $G$ 上のクリーク)Cをノードと呼ぶ。 また、 冗長さを除いた木表で表現上で、 ノード が持つ頂点集合をし、 の所持頂点と呼ぶ。 このとき、 の子孫が持っ頂点はに含まれない。
$v$

$C$

2.2

$\ell(C)$

$C$

木表現

$C$

$\ell(C)$

Ptolemaic Graph $G=(V, E)$ に対して、極大クリークの集合 $M(G)$ と、 $G$ の 2 つ以上の極大クリークの共通部分の集合 $L(G)$ を考える。
このとき、 $C(G)=M(G)\cup L(G)$ で定義される集合 $C(G)$ について以下の補題が存在する。

補題 1. [7] $G=(V, E)$ を Ptolemaic Graphとする。 $C_{1},C_{2}\in C(G)$ が ovelap3 するとき、とはを分割する。

$C_{1}\cap C_{2}$$C_{1}\backslash C_{2}$$C_{2}\backslash C\iota$

Ptolemaic Graph $G=(V, E)$ は、集合 $C(G)$を頂点集合とする、 一意に定まる有向な木表
現 $arrow T(C(G))=(C(G),A(G))$ を持つ [7]。有向辺 (以下、弧) の集合 $A(G)$ は、各クリークの包含関係を表現しており、 弧 $(G, C_{j})$ が $A(G)$ に含まれる必要十分条件は、
らかつ、を満たす が存在しないことである。
欧$C_{i}\subset$$C$$C_{j}$$C_{i}\subset$$C$

lIereditary Graph とは、任意の誘導部分
グラフがにおいて 2 頂点聞の距離が変わらないグラフで$\iota_{Distance}$ある。

2Chordal Graph とは、 少なくとも長さが 4 である
任意のサイクルが必ず弦を持つグラフである。
3 集合 $X$ と $Y$ に対して、 $X\cap Y\neq\phi,X\backslash Y\neq\phi$ そしてが成立するとき、 $X$ と $Y$ は averlap するという。
$Y\backslash X\neq\phi$3ハミルトン閉路問題
以下で ‘ Clique Laminar kee を用いた、

Ptolemaic Graph 上のハミルトン閉路を求める [7] のアルゴリズムについて説明する。 本稿は、ハミルトン閉と呼ぷ。
路問題を木表現における各ノードごとの部分問題に分割し、 それぞれのノードで局所的なハミルトン閉路を計算する。 以下でその計算方法について述べる処理ノードをの親を$i=1,$ $\ldots,p(L)$ とする。 まず簡単のために、$c(L)=0,p(L)\geq 0$ である場合について考え
ではこれを$\mathcal{H}C$$\mathcal{H}C$

$L$

、

$L$

$P_{1},$ $P_{2},$$\ldots,$$P_{p(L)^{\text{、}}}$る。

が持つ頂点を使い、長さ $|L|$ のサイクルを一
時的に 内で形成する。 このサイクルが持っごと}\breve \acute 1 本ずっ割り当て、 そ
辺を、 の親の辺を拡張しての所持頂点を接続することにより、 をサイクルの一部とする (図 2)。補を取
題 1 より、 $G$ から $L(G)$ の要素である

$L$

$L$

$L$

$P_{i}$$P_{1}$$P_{i}$$L$

111
り除くことによって、 $G$ は $p(L)$ 個の連結成分に分解される。 よって次の補題が成立する。

れる余剰辺の数を表す。 以下の議論において、$m(C_{i})$ と $\delta((L, C_{i}))$ は既に計算されているも補題 2. [7] Ptolemaic Graph $G=(V, E)$ ののとする。

Clique Laminar $beearrow T(C(G))$ が与えられた
とき、 $c(L)=0$ である $C(G)$ の要素 $L$ に対しを、 $L$ の所持頂点として利用することが可能である。 まず、 に対して割り当てられているの辺を 1 本切り取り、 $L$ とその親の頂点を使ったサイクルの一部として置き換える (図 3)。もし、 の子のある
に対し
$L$

の子

$C_{i}$$L$$C_{l}$て、 以下のことが成立する。

(i) $|L|\geq p(L)$ のとき、 は $p(L)$ 個の親を接続したサイクルを形成し、 $|L|-p(L)$ 本の辺を余らせることが出来る。
$L$(ii) $|L|<p(L)$ のとき、接続できない親があるため、 $G$ はハミルトン閉路を持たない。

また、余った辺の数を margin $m(L)$ とする。
つまり $m(L)=|P(L)|-p(L)$ である。

Clique Laminar Troe 上のノードは層構造を持っため、 余剰辺は先祖の接続に利用できる。 ノード間の margin の配分は、 distribution を用いて表現する。 -stribution は、それそれの弧 $(C_{j},Ci)\inarrow T(C(G))$ に対して割り当てられる関数$\delta((C_{j},C_{*}\cdot))$として定義される。

$i=1,$ $\ldots,p(L)$ に対して、 それぞれの弧 $(P_{i}, L)$
は、 $\sum_{i=1}^{p(L)}\delta((P_{i}, L))=m(L)$ となるような

distributionを持つ。 各ノード間の親子関係は、 クリークの包含関係を表したものであるため、余剰辺である margin は子から$\delta((P_{1}, L))$$L$

$C_{i}$て $\delta((L, Ci))>0$ ならば、乃を接続するための頂点としてを使うことが出来る。 よってが子を持つ場合の $mar_{\dot{i}^{nm(L)}}$ は、 $m(L)=$$C_{1}$$L$と定義される。 以上の議論から次の定理が導かれる。

$|l(L)|+c(L)+ \sum_{1=1}^{c(L)}\delta((L, C_{i}))-p(L)$定理 3. [7] $G=(V, E)$ を Ptolemaic Graphとする。 $G$ がハミルトン閉路を持つ必要十分
条件は、 $C(G)$ におけるそれぞれのノード $L$ について、 $m(L)\geq 0$ を満たすような margin のdistribution が存在することである@
は未処理の隣接ノードが 1 つになったノードに対して、 局所的なハミルトン路の形
成を逐次行う。 このとき同じノードを複数回処理する必要がないことが、 次の補題からいえる。
$\mathcal{H}C$

補題 3. Ptolemaic Graph $G=(V, E)$ のハミルトン閉路をとす
上の弧を持つ任意の具なるノー
る。 $T(C(G))$
ドを考えたとき、 $G$ のハミルトン閉路
は、 $l(C_{1})$ に含まれる頂点と乏 (C2) に含まれる頂点を接続する辺を高々 2本しか持たないとしてよい。
$(x_{0}, x_{1}, x_{2}, \ldots, x_{k}, x_{0})$親に対してのみ配分可能になる。

$C_{1\text{、}}C_{2}$$(x_{0}, x_{1}, x_{2}, \ldots, x_{k}, x_{0})$証明. 略口図 2: 辺の割り当て

図 3: 親と子の接続

続いて、処理ノード が子を持っとき、つまり $c(L)>0,p(L)\geq 0$ である場合を考
$L$

える。

$L$

$C_{1},$ $C_{2},$の親子をそれぞれ$C_{c(L)}$ で表す。 $i=1,$$P_{1},$ $P_{2},$$\ldots,$$\ldots,$$\ldots,$$c(L)$$P_{p(L)}$

、

$j=$

とすると、 $Ci\subset L\subset P_{j}$ が成立す
このときのる。
における局所的なハミルト
ン閉路の構成法にっいて示す。

$1,$$\ldots,p(L)$$L$

それぞれの弧は、 $d_{\dot{L}}stribution$$\delta((L, C_{1}))$ を持つ。 $\delta((L,C_{i}))$ は、の処理時$(L, C_{1})$$C_{i}$に$C_{i}$

が、$L$に提供可能な辺の余剰分であったの処理においては、 が
から提供さ

が

$L$

$L$

$C_{1}$

補題 3 は、 本稿で取り扱う他の経路問題に関しても同様に成立する。
処理ノード垣こ対して、 唯一の未処理であるの隣接ノードを、次の処理ノード $X$ とす$X$
はを持つノードから計算するため、る。
葉から処理を行う。 $X$ が親であれば、余剰頂点の提供は可能だが、 不足分の要求は出来ない。
よって、 $\delta((X, L))\geq 0$ ならその余剰分を $X$ に伝達し、 $\delta((X, L))<0$ ならハミルトン閉路は無いと判断する。 $X$ が子の場合は不足頂点の要求は可能だが、余りを提供できない。そのため、 $\delta((X, L))\geq 0$ となり余りが発生した場合$L$$\mathcal{H}C$

112
は、 $\delta((L, X))=0$ とし、 不足分は $\delta((L, X))$に正の値として格納してに伝達する。
に対し以上の議論から、 アルゴリズムて次の補題が成り立っ。
$X$$\mathcal{H}C$

補題 4. [7] Ptolemaic Graph $G=(V, E)$ が与えられ、を実行したとする。 このとき $G$ がハミルトン閉路を持つ必要条件は、 $T(C(G))$
上の任意のノード と、 次に処理したノード$X$ に対して、が成立することである。
$\mathcal{H}C$$L$$\delta\geq 0$$G=(V, E)$ とし、 $|V|=n_{\backslash }|E|=m$ とする。
このとき $arrow T(C(G))$ が持つノ $-$ ト*の数 $|C(G)|$を $n’$ と置くと $n’=O(n)$ となり、 アルゴリズム$\mathcal{H}C$は計算時間、 領域ともに $O(n’)=O(n)$である [7]。

る必要がある。事前処理の後、計算済みの distribution を利用し、 $(S, \ldots, T)$ 上の各ノードで局所的なハミルトン路の計算を繰り返す。 の直前に処理したノード $W$ と次に処理するノー
ド $X$ が親か子かによって、 局所的なハミルトン路の構成方法が変わる。
$(S, \ldots,T)$ 上の全てのノードが処理済となり、$L$ハミルトン路があればそれを出力する。そうでなければ、 $C(G)$ に含まれる他の 2 つのノードの組み合わせに対して同様の処理を行う。 $S=$のときは、 ハミルトン閉路を求めることになるため、 以降では $S\neq T$ であるとする。
固定した $(S, T)$ 間の各ノードにおける、 局
所的なハミルトン路の計算について、 サイクルの形成とは異なる部分がある。 処理ノード$L$ において、個の先祖をサイクルの一部として接続するために必要な辺の数は 本である。
しかし、 $L$ 内の頂点を使って一時的にパスを作ると、それだけでは頂点数 $-1$ 本の辺しか得られない。 さらに、 このパスの両端点から辺が伸ばせるかどうかという条件も、 $L$ の直前に処理したノード $W$ と次に処理するノード $X$ が、それぞれ親か子かによって変化する。 これらのことは margin と distribution の計算に影響を

$T$

$k$

$k$

4

ハミルトン路問題

サイクルではなくパスを求めるため、 どの 2
頂点をパスの端点とするか判断するプロセスが必要になる。 そのためハミルトン閉路問題
よりも難しい。

4.1

概要

与える。 詳細な説明は省略する。

提案アルゴリズムをはとする。
$rn_{ee}$ 上のノードの組 $(S, T)$ を
Clique Laminar$\mathcal{H}\mathcal{P}$Ptolemaic Graph $G=(V, E)$ が与えられ、$\mathcal{H}\mathcal{P}$$T(C(G))$ 上のノードの組 $(S, T)$ について$\mathcal{H}\mathcal{P}$を実行したとする。 このとき、以下の補題が成立する。

端点を含むクリークとしたハミルトン路の有無を検査する。
固定した 2 頂点間の処理であること、サイクルではなくパスを求めることを除けば、基本的

補題 5. $G$ が $S,$ $T$ 内に端点を含むハミルトン路を持つ必要条件は、 $(S, \ldots, T)$ 上で最初に処とほぼ同じであり、ハミルトン閉路問題で定義された margin の distributionを利用して解く。

理したノード $S$ と、次に処理したノード $X$ に対して、 $X$ が親のとき $\delta((S, L))\geq-1$ が成立することである。

な手続きは

4.2

$\mathcal{H}C$

動的計回法に着つくアルゴリズム

は、 はじめに Clique Laminar Tree 上
で 2 つのノード $(S, T)$ を固定する。 このとき、$(S, T)$ を端点とする無向のパス $(S, \ldots, T)$ が決$\mathcal{H}\mathcal{P}$まる。 このパス上にあるノードを除く全てのノードに対して、 事前処理として margin のdistribution を計算しておく。 このとき、 mar-gin の不足を要求出来ないノードが存在すれば、$S,$ $T$ を端点を含むクリークとするハミルトン路は存在せず、他の 2 頂点の組み合わせを考え

補題 6. $G$ が $S,$ $T$ 内に端点を含むハミルトン路を持っ必要条件は、 $(S, \ldots,T)$ 上の $S,$ $T$ を除
く任意のノード と、 $L$ の直前に処理したノー
ド W、次に処理したノード $X$ に対して、 以下の条件が成立することである。
$L$(i) $W$ が子かつ $X$ が親のとき、 $\delta((X, L))\geq 0$である。

(ii) $W$ と $X$ が親のとき、 $\delta((X, L))\geq-1$ で
ある。

113
補題 7. $G$ が $S,$ $T$ 内にそれぞれ端点を含むハミルトン路を持つ必要十分条件は、 $(S, \ldots, T)$ 上で最後に処理したノード $T$ に対して、 $m(T)\geq 0$が成り立つことである。

処理ノ -ト の子が持っ利得表について$*$$\bullet$が持つ利得表をの子には、 処理ノード $L$ がとする。
本の辺を要求を管理すしたときに付随する利得には、子孫から得らる配列である。
れる最大利得から、 所持頂点の少ない順$L$$\gamma c_{j}[k]$に $k$ 個のノードの所持頂点の和を差し引いたものが格納されている。

それぞれの利得表が持っ要素の数 (サイズ)と表す。 利得表について、 以を、下の補題が成立する。
$|\delta_{p_{:}}|$

最長閉路問題$|\gamma c_{j}|$5.1

Ptolemaic Graph 上で最長閉路を求めるアを提案する。

は動的計画法に基づき、 Chque Laminar $bee$ 上の各ノードについて局所的な最長閉路の候補を計算する。
処理ノードを $L$ 次の処理ノードを $X$ とする。 $L$ の処理済の隣接ノードは全て、 これまで計算してきた局所的な最長閉路の候補を持つ。
処理済の隣接ノードが持つこの情報は、 利得表と呼ばれる配列によって管理される。利得とは接続可能なパスの長さ表す。以下で利得表について説明する。
$\mathcal{L}C$$21<k<|\delta_{P_{1}}|$$\bullet$$c(L)$$C_{c(L)}$に対して、$(\delta_{P_{i}}[k]-$が成り$\gamma c_{j}[k]\geq\gamma c_{j}[k’]$が成り立つ。

$41<k<|\gamma c_{f}|$ である $k$ に対して、 $(\gamma c_{j}[k-$$1]-\gamma_{C_{j}}[k])\leq(\gamma_{C_{j}}[k]-\gamma_{C_{j}}[k+1])$

が成

り立っ。

証明. 略口また、 実際の処理では処理ノード $L$ に対して、 処理済の親、 子が持つ利得表を全て統合とする。 統合前と後で利し、 それぞれを$\delta$、$\gamma$得表が持つ意味は変化しない。
補題 9. 利得表$\delta_{P:}$と$\gamma c_{j}$は $O(n\log n)$ 時間、$O(n)$ 領域で統合可能であり、統合後の利得表$\gamma$が示す意味は変化しない。

とし ‘$i=1,$

子を$P_{p(L)^{\text{、}}}$$\ldots,p(L)$ 、

$j=$

とする。

5.3

動的計画法に着つくアルゴリズム

上のノードに対する具体的な処理方法を以下に示す。 この局所的な計算は未処理$arrow T(C(G))$

処理ノードの親が持つ利得表にっいての親が持つ利得表をとする。
に 本の辺を提供
は、処理ノード がしたときに得られる利得を管理する配列である。
には、先祖のノードの中で、所持頂点数が大きな順に 個のノードの所持頂点の豹が格納されている。
$L$

$k$

証明. 略口

利得表

処理ノード $L$ の親を $P_{1)}P_{2}$ , ...,$\ldots,$であるが成り立っ。

立っ。

、$\ldots,$$\delta_{P_{1}}[k]\leq\delta_{P_{i}}[k’]$$\delta_{P:}[k-1])\geq(\delta_{p_{:}}[k+1]-\delta_{P:}[k])$$\delta$$C_{1},$ $C_{2},$に対して、 以下のこと$\mathcal{L}C$、

5.2$\gamma c_{\dot{f}}$3 $k<k’$ のとき、

概要

ルゴリズム

$\delta p_{:},$

1 $k<$ 躍のとき、すべての頂点を使うという条件がないため、使わない頂点を選ぶプロセスが必要となり、ハミルトン閉路問題よりも複雑になる。

$1,$

、

補題 8. 利得表が成り立っ。

5$k$$\gamma_{C_{j}}[k]$${}_{n}C_{2}$$\mathcal{H}\mathcal{P}$$\gamma_{C_{j}}$$\gamma_{C_{j}}$$C_{i}$

いずれの場合の処理も、 1 つのノードにかかる処理時間は定数時間内に抑えられることは通り自明である。 $(S, T)$ の組み合わせはあり、 次の定理が導かれる。
定理 4. $G=(V, E)$ を Ptolemalc Graph とし
は $G$ 上のハミルトン路の有無をたとき、$O(n^{3})$ 時間、 $O(n)$ 領域で判定する。

$C_{i}$$P_{i}$$\delta_{P}$$L$$P_{1}$の隣接点が一つになったノードに対して行われ$\delta p_{:}$$k$$\delta_{P:}[k]$$\delta_{P_{1}}[k]$$k$る。 処理ノード $L$ \iota こおいて、 次の処理ノード

を計算
を、子の場合はが親の場合はする。 また の状態により、場合わけを行う。

$X$$\delta_{L}$$\gamma_{L}$$L$(1) 葉の場合$\mathcal{L}C$は、 はじめに Chque Lminar Ttee が持っ114
葉を全て処理する。 この場合、
固を、子 $X$ に伝達する利得表$L$の所持頂点数に格納する。

(2) 葉では無い場合(2-3) $p(L)>0,$ $c(L)>0$ の場合
そして $l(L)$ を用いて統合された利得表$X$ への利得表を構成する。 $p(L)>0$ であるた
め、 $L$ 内で利用できる辺を先祖に振り分ける必要がある。 また、 $c(L)>0$ であることから、 $L$
において利用可能な辺の数は子孫から貰った$\delta$、

葉の処理後、
は未処理の隣接ノードが 1 つになったノードに対して順次処理を行う。今後の議論のいずれの場合においても、 はじめにをそれぞれ統と子の利得表親の利得表合し、 と を得る。
$\mathcal{L}C$$\delta_{P_{i}}$$\gamma_{C_{j}}$$\delta$$\gamma$(2-1) $p(L)>0,$ $c(L)=0$ の場合
このとき、 $L$ に隣接する唯一の未処理ノード$X$ は親となる。
は と $l(L)$ を用いて、 $X$を構成する。 $L$ は子を持に伝達する利得表
たないため、 先祖の接続に使用できる辺の数
は $|\ell(L)|=|L|$ 本である。
$X$ に $k(0\leq k\leq|L|)$ 本渡した場合、 その他の先祖には残りの $|L|-k$ 本を提供できる。
のとき $L$ は、 $X$ を除く親から $\delta[|L|-k]$ 本の辺を受け取って、 長さ $|L|+\delta[|L|-k]$ のサイ
クルを形成し、 これを $X$ に渡すことができる。
よって $\gamma\iota[k]=|L|+\delta[|L|-k]$ とする。 ただ
は $X$ に全く頂点を提供しない場合でし、あり、 $L$ の処理時点で完結した局所的な最長閉を除いた利得表を $X$ に伝路となるため、は完結した最長閉路の候補を格達する。
納する配列 $LC$ に別個格納する。
$\mathcal{L}C$となる。

$\delta_{L}$$\delta$$\gamma_{L}$こ$\gamma_{L}[0]$$\gamma_{L}[0]$$\gamma_{L}[0]$$\gamma$、辺数によって決まる。そのため、はじめに子孫全体から $h(0\leq h\leq|\gamma|)$ 個の頂点を受け取った場合の、 先祖の接続に使用可能な頂点を表
す $S_{h}(L)$ を計算する。 以下で、 このときに $X$が親である場合と子である場合の処理方法について、 それぞれ示す。

(2-3-1) $X$ が親の場合と利得表 を用いて、 $X$ への利得表悔を作成する。 このとき、 $L$ で使用可能な辺数は$S_{h}(L)=|L|+c(L)+h$ で定義される。 を固定し、 $S_{h}(L)$ から 本の辺を $X$ に提供した場$S_{h}$$\delta$$h$$k$

合について、利得表$\gamma\iota$に格納する値を計算していく。
内で使用可能な辺数を $S_{h}(L)$ として固定するため、その後の基本的な処理の流れは $p(L)=$かつ $c(L)>0$ の場合と同様である。 $X$ に本の辺を渡したとき、 その他の先祖 (つまりには $S_{h}(L)-k$ 本の辺が提供可能であり、$\gamma_{L}[k]=|L|+\gamma[h]+\delta[S_{h}(L)-k]$ とする。 ただし、 $(S_{h}(L)-k)>|\delta|$ の場合、 に提供する
$L$

$k$

$0$

$\delta)$$\delta$

辺の数が接続可能な先祖のノードの数を超えているため計算する必要がない。
この手続きは を固定したものであるため、同様の処理を全ての \dagger こ対して行う。 $X$ にに格納され個渡したときの利得は、既にのている値よりも大きければ更新する。
要素があればそれを配列 $LC$ に保存する。
$h$

$h$

$k$

$\gamma_{L}[k]$$\gamma_{L}[0]$(2-2) $p(L)=0,$ $c(L)>0$ の場合
このとき、 は葉ではないルートであり、未処$L$理である唯一の隣接ノード $X$ は子となる。 $L$
は親を持たないため、 から少なくとも 1 本の辺を拡張出来れば、 $X$ を含む $L$ 内の頂点を全て接続可能である (図 5)。表中で最大利得を持$\gamma$を選択した場合でも、少なくとも処理済の子の数だけ辺が自由に使えるので、 この場合のみを考える。 よって、 $\gamma[c(L)]$ と $|L|$ の和をに格納する。っまり $\delta_{L}[1]=|L|+\gamma[c(L)]$つ $\gamma[c(L)]$$\delta_{L}$(2-3-2) $X$ が子の場合に渡す利得表を構成する。 このとき $X$がの子であるため、 $L$ で使用可能な辺数は$S_{h}(L)=|L|+c(L)+h+1$ と表される。 $X$ が親の場合と同様、 先祖をっなぐ為に $S_{h}(L)$ から何個の頂点を使うのか、 全ての h\downarrow こついて考える。
$X$ 自体はの子であるため、 $S_{h}(L)$ は全て$X$$\delta_{L}$

$L$

$L$

に配分すればよい。 よって、 $\delta_{L}[1]=|L|+$$\gamma[h]+\delta[S_{h}(L)]$ となる。 このとき、
本であ$|\delta|>S_{h}(L)$の辺が先祖から得られるが、$\delta$$\delta[S_{h}(L)]$115
るときは接続できていない先祖が存在する。そのため、に未使用の の要素を加えていきを完成させる。 つまり $k>1$ に対し、 $\delta_{L}[k]=$$\delta$$\delta_{L}$$\delta_{L}$$\delta_{L}[k-1]+\delta[S_{h}(L)+k-1]-\delta[S_{h}(L)+k-2]$となる。

ドの処理時間は $O(n^{2})$ である。 よって、 全体の計算時間は $O(n^{3})$ となる。 また、 利得表のサイズは高々 であり、 これを全ノードが持っ口とすると計算領域は $O(n^{2})$ となる。
$n$について、 上記の利得表の計算を行う。 ある について計算した利得表
は、 既に格納されている値より大きければ更が出力するのは最長閉路の長さであるが、実際の最長閉路の出力も可能である。

新する。

6

全ての

$h$

$\delta_{L}$$k$$\delta_{L}[k]$(3) 最後のノ – ト v の場合が最後の処理ノードであるとき、 から何個の頂点を使い、 の所持頂点とあわせて から何個の頂点を獲得したか、 全ての組み合わせを列挙し、配列 $LC$ に格納する。配列 $LC$ の要
素の中で最大のものが、 $G$ の最長閉路の長さとして得られる。
以上の議論により、 次の補題が成立する。
$L$$\gamma$$L$$\delta$$\mathcal{L}C$

最長路問題

Ptolemaic Graph における最長路問題は、前述したハミルトン路問題と最長閉路問題を組み合わせた問題であり、パスの端点を求める手
続きと、 頂点を選別する手続きが必要になる。
従って、 この 2 つの問題を解くアルゴリズムを組み合わせることで解決可能になる。

補瑠 10. Ptolemaic Graph $G=(V, E)$ の最6.1

長閉路として $(x_{0}, x_{1}, x_{2}, \ldots, x_{n}, x_{0})(0\leq i,$ $j\leq$を実行したとき、 $T(C(G))$ 上n) を考える。

は提案アルゴリズムをとする。
$arrow
T(C(G))$と同様に、上の固定した 2 つのノー
ド $(S, T)$ を端点を含むクリークとした最長路を求める。 この作業を全ての頂点の組み合わせに対して行い、 最も多くの頂点を使用した
パスを $G$ の最長路として出力する。 $S=T$ のときは、最長閉路を求めることになるため、以降では $S\neq T$ であるとする。
を利用し、 $(S, \ldots, T)$
は前処理として上のノード以外のノードに対して、利得表 と$\mathcal{L}C$のノード $L$ と、 次に処理されたノード $X$ に対
かっ $Xj\in X$ であるとする。
して、のとき、 以下のことが成立する。
$x_{\mathfrak{i}}\in L$$\bullet$こ$L$が $p(L)=0$ かつ $c(L)>0$

つ$c(L)>0$ かつ $X$ が子であるとき、 $L$ は、$p(L)>0$ か

利得表
を持ち、
は、 $X$ が $L$ に本の辺を提供したときに得られる利得を表す。
$\bullet$$k$$\delta_{L}[k]$$\delta_{L}$が $p(L)>0$ かつ $c(L)=0$ $p(L)>0$ か
つ $c(L)>0$ かつ $X$ が親であるとき、 $L$ は
$L$

、

利得表

$\gamma_{L}$を持ち、$\gamma_{L}[k]$は、 $X$ が $L$ に$k$

本の辺を受け取ったときに付随する利得を表す。

定理 5. $G=(V, E)$ を Ptolemalc Graph とし
は $G$ の最長閉路の長さを $O(n^{3})$ 時
たとき、間、 $O(n^{2})$ 領域で計算する。
$\mathcal{L}C$$10$ より、 各ノードの処理の略証. 補題際、 親と子の利得表から最大利得を連結する
ことで、処理ノードが持つ利得表を $O(n)$ 時間
で構築 (更新) 出来る。 $p(L)>0$ かつ $c(L)>0$の場合は、 の取り方が高々 通りあり、 その$h$、$\mathcal{L}\mathcal{P}$$\mathcal{L}\mathcal{P}$$\mathcal{H}\mathcal{P}$$\mathcal{L}C$$\mathcal{L}\mathcal{P}$$\delta$\gamma (局所的な最長閉路の候補を格納した配列) を計算しておき、 $(S, \ldots, T)$ 上のノードに伝達す
ト*L に対する手続る。 $(S, \ldots, T)$ 上の処理ノ
きは、 直前の処理ノード $W$ と次の処理ノード$X$ の状態によって場合分けされる。 それぞれを利用した処理を行う。
の場合において、が求めるのは $(S, \ldots,T)$ 上のノードを使用した最長路である。 よって、直前の処理ノー
ド $W$ と、次の処理/– ト $X$ に対しては、 は少なくとも辺を 1 本ずつ提供、 または受け取り、 $(S, T)$ 間のパスが途切れないようにする必要がある。
また、切はサイクルを求める手続きである
ため、 これをパスの形成に利用できるようにする必要がある。そのため、 内で利用可能な辺の数の調整をそれぞれの について行う。
ー$\mathcal{L}C$

証明. 略口

$8$

概要

$9$

、

$n$

数だけ利得表の計算を行うため、 1 つのノー$\mathcal{L}\mathcal{P}$

$L$

$L$

$L$

116
6.2

動的計回法に基づくアルゴリズム

参考文献

基本的には
と
の組み合わせとなる
アルゴリズムのため、 処理ノード で利用可$\mathcal{H}\mathcal{P}$$\mathcal{L}\mathcal{L}$$L$

能な辺の数の調整について示した補題のみを記載し、 詳細は省略する。
補題 11. Ptolemaic Graph $G=(V, E)$ の最長路として $(x_{0}, x_{1}, x_{2}, \ldots, x_{n})(0\leq h, i,j\leq n)$ を考える。 ある $(S, T)$ を固定して LP を実行した
とき、 $T(C(G))$ 上のノード $S$ $T$ $L$ $L$ の直前に処理されたノード $W$ 次に処理されたノード $X$ に対して、 $x_{0}\in S$ $x_{n}\in T$ $x_{h}\in W$$x_{i}\in L$ かつ $Xj\in X$ であるとする。 このとき、以下のことが成立する。
、

、

、

、

、

(i)

、

、

に対して、 が $S$ かつ $X$ が親、 が $T$
かっ $W$ が親、 $W,X$ が親であるとき、内で利用可能な頂点数 +1 本の辺が先祖の接続に利用可能。

$L$

$L$

$L$

$L$

(ii)

(iii)

に対して、 が $S$ かつ $X$ が子、 $L$ が $T$ か
つ $W$ が子、 $W$ が子かつ $X$ が親、 $W$ が親
かつ $X$ が子であるとき、 $L$ 内で利用可能な頂点数分の辺が先祖の接続に利用可能

$L$

$L$

$L$

に対して、 $W,$ $X$ が子であるとき、 $L$ 内

で利用可能な頂点数-1 本の辺が先祖の接続に利用可能を組みあわせたアルゴリ
の処理を、
時間かかる
ズムであり、$7_{(}c(G))$ 上の全てのノードの組に対して行う。
よって次の定理が成立する。
は$\mathcal{L}\mathcal{P}$と$\mathcal{H}\mathcal{P}$$\mathcal{L}C$$O(n^{3})$$\mathcal{L}C$

定理 6. $G=(V, E)$ を Ptolemaic Graph とし
は $G$ の最長路の長さを出力し、計たとき、$\mathcal{L}C$

算時間は $O(n^{5})$$\mathcal{L}\mathcal{P}$、

計算領域は $O(n^{2})$ である。

が出力するのは最長路の長さであるが、実際の最長路の出力も可能である。

[1] Maw Shang Chang, Shaur Ching Wu,
Gerard J. Chang and Hong Gwa Yeh,
Hamiltonian Problems on Ptolemaic
Graphs, Proceedings of Workshop on AlgorIthms and $Th\infty ry$ of Computation, International Computer Symposium, Chiayi, Taiwan, R.O.C., pp.27-34, 2000.
[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein,
Introduction To Algorithms Second Edition, The MIT Press, 2001.
[3] Martin Charles Golumbic, Algorithmic
Graph Theory and Perfect Graphs Second Edition, Elsevier B.V.,.
$2\infty 4$[4] Reinhard Diestel,Graph
Springer-Verlag, 1997.

[5] Edward Howorka, A Characterizationof Ptolemaic Graphs, Journal ofGraphtg$Th\infty ry,$ $5:323-331$ , 1981.
[6] Ryuhei Uehara and Yushi Uno, Efficient Algorithms for the Longest Path
Problem, l5th Annual International Symposium on Algorithms and Computb
tion (ISAAC 2004), Lecture Notes inCompllter Science Vol. 3341, pp.871-883,

2004.
[7] Ryuhei Uehara and Yiishi Uno, Laminar
Structure of Ptolemaic Graphs and Its
Applications, 16th Annual International
Symposium on Algorithms and Computation (ISAAC 2005), Lecture Notes in
Computer Science Vol. 3827,. pp.186-195,

2005.

7

まとめ

本稿では、木表現を用いて Ptolemaic Graph
上のハミルトン路、 最長 (閉) 路問題を解く多項式時間アルゴリズムを提案した。 今後の課
題は各アルゴリズムの計算時間領域の改善と、 Distanoe Herffltary Graph 上の最長 (閉)路問題の解決が挙げられる。

Theory,