数理解析研究所講究録
第 1894 巻 2014 年 53-57
2013 年度冬の LA シンポジウム [S4]53

パリティハミルトン閉路問題

Parity Hamiltonian Cycle Problem
西山宏

山内由紀子

来嶋秀治

山下雅史

Hiroshi Nishiyama

Yukiko Yamauchi

Shuji Kijima

Masafumi Yamashita

九州大学

Kyushu University

1

はじめにうため，連結無向グラフを以下単にグラフと書く．の部分グラフ $H$ について，その頂点集合と辺集$G$

ハミルトン閉路問題は，$\mathcal{N}\mathcal{P}$完全な問題の代表的なものであり，いくつかの十分条件，必要条件が明らかにされつつも，“ 良い特徴づけ” の発見には至っていない．本発表では，ハミルトン閉路問題の一つの一般化として，パリティハミルトン閉路問題を導入する．ハミルトン閉路が各頂点を一度ずつ訪問する全域巡回路であるのに対し，パリティハミルトン閉合をそれぞれ $V(H),$ $E(H)$ で表す．グラフ $G$ において頂点$v$存在性を決定する問題である．

本予稿では，パリティハミルトン閉路問題ならびにその最適化問題について，主にその多項式時間解決可能性，およびアルゴリズムについて考察する．2
章で本予稿で用いる記法や用語，およびパリティハミルトン閉路問題の定義を行う．3 章では制約のない場合のパリティハミルトン閉路問題について議論し，4 章では辺の通過回数に制約をっけた問題について考える．

$N(v),$ $\delta(v)$と表す．グラフから頂点と定義

2.1

用語・記法

頂点集合 $V$ , 辺集合 $E$ をもつ無向グラフを $G=$$v$$v$で表す．本予稿では連結無向グラフのみを扱と表す．いずれ$G$と頂点$v$について，$G$と表記する．

正整数 と辺集合- に対し， の各辺 を 個含$v$$E$$k$$E$$e$$k$

むような多重集合を $kE$ と書く．このとき，単純グ
ラフ $G$ に対し，
$G_{k}=(V, kE)$ を $G$ の$k$重グラフと呼ぶ．

2.2$T$-join

グラフ $G=(V, E)$ に対し頂点集合 $T\subseteq V$ が与えられたとき， のすべての頂点の次数が奇数となり，かつその他の頂点の次数がすべて偶数となるような辺の部分集合を -join と呼ぶ．すなわち，辺集合$T$$T$に対し $K=(V, J)$ とおくと，$d_{K}(v)\equiv[Matrix]$(1)$JI$ まにおける -join である． にを満たすとき，-join が存在するための必要十分条件は， が偶$G$$T$$(V, E)$$\delta_{G}(v)$に接続するすべての辺を取り除いてできるグラフを $G$$J\subseteq E$2と隣接している頂点の集合を $N_{G}(v)$ , 頂点も考えているグラフ $G$ が明らかである場合は，単に路は各頂点を奇数回訪問する全域巡回路である．パリティハミルトン閉路問題は，このような巡回路の$v$に接続している辺の集合を数であることである．

$T$

$G$

$|T|$

542.3と定めて巡回路を構成する．このようにして作った

パリティハミルトン閉路問題

パリティハミルトン閉路問題とは，入カグラフ

巡回路は連結であり，かつ$G$$G$ の全ての頂点を奇数回訪問する巡回路がに対し，存在するかを判定する問題である．そのような巡回$T$の全ての頂点を奇数回$|V|-1$ 個以上の頂点を奇数回訪問する．すなわち，訪問する巡回路は必ず存在する口路のことをパリティハミルトン閉路と呼ぶ．パリティ

補題 3.3. 頂点数が偶数または奇閉路をもつグラフ

ハミルトン閉路では，ハミルトン閉路と異なり，同はパリティハミルトン閉路をもつ．

じ辺を何度通過してもよいとする．辺の通過回数に証明．頂点数が偶数の場合，補題 3.2 における巡回制限を設けた場合の考察は 4 章で行う．MAX-パリティハミルトン閉路問題とは，パリティハミルトン閉路問題を最適化問題の形に直したものである．すなわち，入カグラフ $G$ において，巡回路を構成する
とき，奇数回訪問できる頂点の最大個数を求める問路の構成法から明らか．
頂点数が奇数かつ奇閉路 $C$ をもつグラフを考える．このとき，はじめに $C$ に属すすべての辺いて $x_{e}arrow 1$

巡回路を MAX-パリティハミルトン閉路と呼ぶ．
$G$$x_{e}$$T=\{v\in V|visit(v)\equiv 0$とする．
$T$

$J$

上の巡回路に対し，辺 $e\in E$ を通過する回数をで表す．また，頂点visit$v$の訪問数を$(v)= \frac{1}{2}\sum_{e\in\delta(v)}x_{e}$$x_{e}arrow\{\begin{array}{l}1if e\not\in J かつ e\in E(C)2if e\in J かつ e\not\in E(C)3 if e\in J かつ e\in E(C)4 if e\not\in J かつ e\not\in E(C)\end{array}$(2)とする．この巡回路は連結かつ全ての頂点を奇数回で定める．

3につ(mod2) とおいて， -join を構成し，補題 3.2 と同様に x。の値を増加させる．すなわち，$\}$題である．奇数回訪問する頂点の個数を最大化する

$e$

訪問する

口

補題 3.4. 頂点数が奇数の二部グラフはパリティハ

制約なしパリティハミルトン閉ミルトン閉路をもたない．

路問題$G=(V, E)$ を頂点数が奇数の二部グラフと証明．

する．

$Gl\grave{\grave{1}}\nearrow\backslash ^{o_{1}})$

本章では，辺の通過回数に制約がない場合のパリティハミルトン閉路問題について考察する．
定理 3.1. (MAX-) パリティハミルトン閉路問題はティハミルトン閉路をもつと仮定す

ると，$\sum_{v\in V}visit(v)\equiv\sum_{v\in V}1\equiv|V|\equiv 1$(3)$(mod 2)$多項式時間で解ける．

定理 3.1 を示すため，いくつかの補題を示す．

$G$ は二部グラフであるから，$V$が成り立つ．一方，の二部分割を $A,$ $B$ とすると，補題 3.2. 任意のグラフ $G=(V, E)$ は $|V|-1$ 個以$\sum_{v\in A}visit(v)=\sum_{v\in B}visit(v)$上の頂点を奇数回訪問する巡回路をもつ．

$T=V$ とおく．ただし
証明．

$|T|$.

(4)が奇数のときは， (4) より，$T$ から取り除くとする．
適当な頂点 $v\in T$ を選び，$G$に $T$-join $J$ を構成し， を$\sum_{v\in V}visit(v)$$= \sum visit(v)+\sum_{v\in B}visit(v)$$x_{e}$$=2 \sum_{v\in A}^{v\in A}visit(v)\equiv 0 (mod 2)$.

$x_{e}arrow\{\begin{array}{l}2if e\in J4 if e\not\in J\end{array}$

(5)

55
$G$ はパリティハミルト
これは (3) と矛盾するため，付け) は Fleury のアルゴリズム [3] によって多項式ン閉路をもたない時間で行える

口

口

MAX-パリティハミルトン閉路の構成アルゴリズムをアルゴリズム 3.1 に示す．

4

辺を通る回数に制約の付いたパAlgorithm 3.1 MAX-パリティハミルトン閉路のリティハミルトン閉路問題$\frac{構成}{/^{*}初期化^{}*/}$

本章では，辺の通過回数に制約のついたパリティハミルトン閉路問題について考察する．すなわち，辺の通過回数の上限 を定め，

for all $e\in E$ do$k$$x_{e}arrow 0$

end for$x_{e}\leq k$, for all $e\in E$(6)$/*|V|$ が奇数かつ $G$ に奇閉路があるならば奇閉路を満たすような巡回路のみを許す．

を一周 $*/$

if $|V|$ が奇数 and に奇閉路
for all $e\in E(C)$ do$G$$C$が存在 then定理 4.1. $k\geq 4$ のとき，パリティハミルトン閉路問題は多項式時間で解ける．

$x_{e}arrow 1$

証明．アルゴリズム 3.1 が多項式時間で終了するこ

end forend ifとから明らか$Tarrow\{v\in V|visit(v)$ が偶数

if$|T|$$\}$が奇数 then

口定理 4.2. $k=1$ のとき，パリティハミルトン閉路問題は$\mathcal{N}\mathcal{P}$完全．

$v\in T$ を選び $Tarrow T\backslash \{v\}$$k=1$
証明．最大次数が 3 以下のグラフにおいては，

end if$/*$

訪問数が偶数の頂点間に往復路を追加 $*/$-join を構成
for all $e\in J$ do
$T$

$J$

$\mathcal{N}\mathcal{P}$$k=1$ のパリティハミルトンである．したがって，$x_{e}arrow x_{e}+2$閉路問題もend for$/*$でのパリティハミルトン閉路問題はハミルトン閉路問題と等価である．[1] によると，平面的 3-辺連結 3正則グラフにおけるハミルトン閉路問題は完全$\mathcal{N}\mathcal{P}$完全である．口

巡回路を連結にする $*/$

for all $e\in E$ do
if $x_{e}=0$ then

1.1

パリティハミルトン閉路は，グラフの全ての頂点$x_{e}arrow 4$end if
end for
各 $e\in E$ を

modulo factor$v$について $\sum_{e\in\delta_{G}(v)}x_{e}\equiv 2(mod 4)$ を満たす連結な辺集合と見なせる．言い換えれば，パリティハミ$x_{e}$回通過する Euler 閉路を構成$f:Varrow\{0,1,2,3\}$ が $f(v)=$
ルトン閉路問題とは，$2$

for all $v\in V$ であるとき， の$G$$k$

重グラフ$G_{k}$において定理 3.1 の証明．アルゴリズム 3.1 が多項式時間で終了することを示せば十分．頂点数の偶奇および奇閉路の存在性の判定，-join の構成はすべて $O(|V|+|E|)$
時間で可能である．また，Euler 閉路の構成 (向き$T$$\forall v\in V,$$|\delta_{G_{k}}(v)\cap F|\equiv f(v)$$(mod 4)$(7)を満たす連結な辺集合 $F\subseteq E(G_{k})$ の存在性を判定する問題と言える．この$f$を一般化したときに，式56(7) を満たすような辺集合を， の modulo factor$G$かつ$x_{e},$として定義する．いような
定義 4.3 (modulo factor). グラフ $G=(V, E)$ と$f:Varrow\{0,1, \ldots, d-1\}$$E$に対して，辺部分集合$F\subseteq$が$(mod d)$(8)の $mod df$ -factorと呼ぶ．

$|\delta_{G}(v)\cap F|\equiv f(v)$$F$ をを満たすとき，$G$

定義 4.4 (万能性). グラフ $G$ 上において，任意の$f:Varrow\{0,1, \ldots, d-1\}$(ただし$\sum_{v\in V}f(v)\equiv 0(mod 2)$を満たすものに限る) に対$d$が偶数のときはして連結 $mod df$-factor が存在するとき，グラフ$G=(V, E)$ は $mod d$ で万能であるという．

$\ldots,$$x_{e_{1}}$が高々 1 個しか存在しなが存在することを確かめれ
口定理 4.8. $G$ が次の条件を満たす耳分解をもつとき，は $mod 4$ で万能である．

.

・全ての耳の長さが 7 以下である．
最後の耳が$K_{3}$である．

証明．補題 4.6,4.7 より明らか

口定理 4.9. $G=(V, E)$ 力 $i2$ -辺連結弦グラフのとき，$G_{3}$Il $mod 4$ で万能であ 6.
証明略

証明

補題 4.5. $G$ が $mod 4$ で万能ならば $G$ は $k=1$ でパリティハミルトン閉路をもつ．

$x_{e_{1}},$ $x_{e_{2}},$$i$

ばよい$G_{3}$$\forall v\in V,$$=0$ となるような

口2-辺連結弦グラフに対する $k=3$ でのパリティハ

ミルトン閉路の構成アルゴリズムをアルゴリズム 4.1に示す．

$G$ は$G$ が万能であることから，証明．

定理 4.10. $G=(V, E)$ が 2-辺連結$f(v)=2, \forall v\in V$

かつ $G$ が奇閉路をもつとき，$G_{3}$なる $f$ に対する連結 $mod 4f$ -factor をもつ．そのよ$P_{4}$-free グラフ

は $mod 4$ で万能である．

うな factor は全頂点を奇数回訪問する巡回路を与える

口$k=3$ のもとで， の万能性について考察
以下，する．すなわち， が mod4 で万能であれば，証明．証明略

口$G_{3}$$G$$G_{3}$

5

まとめと今後の課題

は $k=3$ でパリティハミルトン閉路をもつ．

本予稿では，パリティハミルトン閉路問題を導入
補題 4.6. $G=K_{3}$ のとき， は mod4 で万能でし，その計算量とアルゴリズム，またパリティハミルある．

トン閉路が存在するための条件について考察を行っ$G_{3}$

証明．実際に全ての$f$に対して連結 $mod 4f$ -factorが作れることを確認すればよい

口た．また，modulo factor と万能性の概念を導入し，$mod 4$ においてグラフが万能であるための十分条件について考察した．

補題 4.7.

$G_{3}$が $mod 4$ で万能であるとする．この$G$ に長さ 7 以下の耳を加えたグラフ $G’$ につとき，いて，$G_{3}’$も $mod 4$ で万能である．

今後の課題としては，辺の通過回数に制約を設け$k=2,3$ での時間計算量の考察がた問題において，挙げられる．また，Jump System[2] 等の代数構造証明．計算機実験によって確かめられる．すなわち， を用いた最適化についても考えていきたい．
長さ 7 以下の耳 $P=e_{0}v_{1}e_{1}v_{2}e_{2}\ldots v_{l}e_{l}(l\leq 6)$ に対するすべての $f:V(P)arrow\{O, 1,2,3\}$ に対して，$x_{e-1}:+x_{e_{i}}\equiv f(v_{i})$$(mod 4)(1\leq i\leq l)$

57
参考文献
[1] M. R. Garey, D. S. Johnson, R. E. Tarjan,“The planar Hamiltonian circuit problem is $NP$complete,” SIAM Journal on Computing, 5(4),704-714, 1976.

-[2] Y. Kobayashi, K. Takazawa: “Even factors, jumpsystems, and discrete convexity,” Joumal of Combinatorial Theory , 99(2009), 139-161.
$B$

Algorithm 4.12-辺連結弦グラフにおける $k=3$$\frac{でのパリティハミルトン閉路の構成}{/^{*}初期化^{}*/}$

for all $e\in E$ do$x_{e}arrow 0$

end for$Harrow G$

完全消去列$v_{1},$$v_{2},$$\ldots,$$v_{n}$を見つける

for $i=1$ to $n-3$ do$Uarrow N_{H}(v_{i})$$U=\{u_{1}, \ldots, u_{m}\}$とする$x_{v_{i}u_{1}}arrow 2$

if $\sum_{e\in\delta_{G}(v)}:x_{e}\equiv 0(mod 4)$ then$x_{v_{i}u_{2}}arrow 2$

end if$Harrow H-v_{i}$end for
三角形 $v_{n-2}v_{n-1}v_{n}$ において，$\sum_{e\in\delta_{G}(v_{i})}x_{e}\equiv 2$(mod4)$(i = n 2, n 1, n)$$x_{v_{n-2}v_{n-1}},$ $x_{v_{n-1}v_{n}},x_{v_{n}v_{n-2}}$のうち高々 1 個となるように $x_{v_{n-2}v_{n-1}},$の値を決める$0$$j3>\prime\supset$となるものが$x_{v_{n-1}v_{n}},$ $x_{v_{n}v_{n-2}}$[3] L. Lesniak, O. R. Oellermann, “An Eulerian Exposition, “ Journal of Graph Theory, 100(1), 277297, 1986.