53

グラフの色付きトークン整列問題について
金野 駿人 1,†鈴木 顕 1,‡

伊藤 健洋 1, ¶*山中 克久 2,§

周 暁 1,‖

1東北大学大学院情報科学研究科
2岩手大学理工学部

Hayato Konno1,†

Akira Suzuki1,‡
Takehiro It o 1,\P

Katsuhisa Yamanaka2,§

Xiao Zhou1,‖

l Graduate School of Information Sciences, Tohoku University
2 Department of Systems Innovation Engineering, Iwate University

1

はじめに

あみだくじとは古くから伝わるくじの方式の1つであり,図1(a) に例示するように,い
くつかの縦線と,隣り合う2本の縦線の間に挿入されたいくつかの横線から構成される.あみだくじは,数字列の置換を与えるともみなせる.すなわち,それぞれの縦線の上端に異なる数字が割当てられ,縦線に沿って数字が下向きに伝わる.伝わる途中に横線があったならば,その横線が接続している2つの縦線を伝わっている数字が交換され,その後改めて下向きに伝わる.このような数字の交換を繰り返し,縦線の下端まで全ての数字が伝わったとき,置換された数字列を得る.

本稿では,あみだくじを設計することを考える.これは,あみだくじの上端および下端の数字列が与えられたときに,最小何本の横線を挿入することで所望の置換を実現するあみだくじが設計できるかを求める問題であり,古くから研究されている [4, 7]. このあみだく
じ設計の問題は,グラフを用いて定式化できる [10]. 具体的には,図1(b) に例示するように,各縦線を頂点とし,隣接する2つの縦線に対応する2頂点を辺で結ぶことでパスを構成する.また,各縦線の上端 (または下端) に割り当てられた数字 i を,対応する頂点上へ色i のトークンを配置することで表す.すると,あみだくじの横線を挿入することは,グラフにおいて隣接する頂点上のトークンを交換することに相当する.したがって,最小本数の横線によるあみだくじの設計問題は,パスに対し初期および目標のトークン配置が与えられた*

本研究は JST CREST JPMJCR1402および JSPS 科研費 JP16K00002,

JP17K12636 の支援を受けたものである.
\dag er

hayato. konno.pl@dc.tohoku.ac.jp\d ag er_{a} . suzuki@ecei.tohoku.ac.jp§yamanaka@cis.iwate‐u.ac.jp
takehi \Gamma o@ecei.tohoku.ac.jp
llzhou@ecei.tohoku.ac.jp\Gamma

JP16K00003,

JP16K00004,

54
2

3

4

1

1

2

3

4

期

1

(a)

1RR34×_{2}

目標

(b)

図1: あみだくじのグラフへの変換の例.(a) 基となるあみだくじ.(b) 対応するパスとトークンの交換.

とき,初期配置から目標配置へ到達するために隣接する頂点上のトークンを最小で何回交換させればよいかという問題に相当する.

トークンを配置するグラフはパスに限らず,一般のグラフへ拡張することができる [10].
この問題は,サイクル [4] , 完全グラフ [4], 完全二部グラフ [10], Star‐Path グラフ [6] に対しては,多項式時間で解けることが知られている.一方で,二部グラフに対してはNP 困難であることが知られている [6].
1.1

色付きトークン整列問題と既知の結果

前述の問題では,全てのトークンは異なる色を持っていた.すなわち,

れば,トークンに現れる色はnn頂点グラフであ種類である.一方で,Yamanaka ら [11] は,この問題を一般化した色付きトークン整列問題を提案した.この一般化では,同じ色を持つトークンが複数枚あることが許される.すなわち,入力としてグラフ G=(V, E) , 色数 c のトークン配

置ん, f_{t}:Varrow\{1,2, c\} , 非負整数 \ell\geq 0 が与えられたときに,高々 \ell 回の隣接するトークンの交換でんからゐへ到達可能かどうか判定する問題である.

この問題は近年提唱されたばかりであるが,グラフクラスに基づく計算複雑性 [1, 4, 11],
パラメータ複雑性 [1, 11] , トークン交換回数 \ell の近似 [9] 等,様々な研究がなされている.
ここでは,本稿に直接関連する既知の結果のみに触れ,その他は省略または表1, 2にまとめる.

表1: 色付きトークン整列問題に対する既知の結果.ここでは,グラフクラスに基づく計算複雑性についてまとめており,
入カグラフの頂点数である.

c\geq 3 であるとする.また,

n

は

55
表2: パラメータ複雑性に関する既知の結果 [1]. ここで表中の \ell, \triangle , tw, diamはそれぞれトークン交換回数,入カグラフの最大次数,木幅,直径を表している.

色数 c が入力であるとき,完全グラフに対してさえNP 完全であることが知られている [1].
一方で,完全グラフに対しては,色数 c をパラメータとした FPT アルゴリズムが与えられている [11]. 色数 c\geq 3 が定数であるとき,n頂点サイクルに対して 0(n^{c+2}) 時間で解け [11],これは色数 c をパラメータとした XP アルゴリズムとみなせる.なお,色数 c=2 であるときには,任意の n 頂点グラフに対して 0(n^{3}) 時間で解ける [11].
この他にも,表2に示すようにパラメータ複雑性は解析されていたが [1] , それらは主としてトークン交換回数 \ell をパラメータとしたものであり,色数 c については上述の完全グラ
フとサイクルに対する結果のみであった.

1.2

本稿の結果

本稿では,色付きトークン整列問題に対し,色数 c をパラメータとした際のパラメータ複雑性を解析した.本稿の結果は図2にまとめられるが,具体的には次の通りである.

まず,スプリットグラフに対して,色数を3以上の任意の定数に制限しても色付きトーク
ン整列問題は NP 完全であることを示した.これにより, P\neq NP の仮定の下では,スプリッ
トグラフに対しては,色数 c をパラメータとしたXP アルゴリズムさえもないといえる.これとは対照的に,コグラフに対しては,色数 c をパラメータとしたXP アルゴリズムを与えた.また,完全二部グラフに対しては,色数 c をパラメータとしたFPT アルゴリズムを与えた.ただし,完全二部グラフに対する計算複雑性は,今のところ明らかになっていない.

NP完全

1

‐ ‐XP ‐

図2: 色数 c によってパラメータ化された色付きトークン整列問題に対する結果.ここで,グラフクラス A とに包含されることを示している.

B に対し,

Aarrow B は,グラフクラス B が A

56
2

定義と準備

グラフ G=(V, E) を重みなし単純無向連結グラフとする. G の頂点集合を V(G) , 辺集
合を E(G) と書くこともある. C を色集合とし, |C| を色数と呼ぶ. G の各点に C に含まれる色を割り当てる写像 f:Varrow C は,

G に対するトークン配置と呼ばれる.

グラフ G に対する2つのトークン配置 f と f' が隣接しているとは,ただ1本の辺 uv\in E(G)が存在して,

G の各点

w\in V(G) に対し次の式を満たすことをいう.

f'(w)=\{ begin{ar ay}{l f(u) w=vのとき; f(v) w=uのとき; f(w) その他． \end{ar ay}
G の隣接するトークン配置の系列は,トークンの交換を行った辺の系列で表せる.

クン配置 f から,辺 s_{1}, s_{2},

G のトーs_{r}\in E に対して順にトークンの交換を行って得られる G の

トークン配置を f' とする.このとき,辺の系列 \{s_{1}, s_{2}, \mathcal{S}_{r}\} は, f から f' へのトークン
交換系列と呼ばれる.また,このトークン交換系列の長さは r と定義される. G のトークン
配置 f から f' へのトークン交換系列のうち,最小の長さをdist (f, f') と書く.ただし,ら f' へのトークン交換系列が存在しない場合には,dist (f, f')=+\infty と定義する.

グラフ

G のトークン配置

fかf から f' へのトークン交換系列が存在するとき,すなわちdist (f, f')\neq+\infty であるとき, f と f' は到達可能という.Yamanaka ら [11] は, f と f'が到達可能であるための必要十分条件が,どの色のトークンも f と f' において枚数が一致
していることであると示した.さらに,グラフの頂点数を n としたとき, f と f' が到達可能であるならばdist (f, f')=0(n^{2}) であることを示した.

グラフ G の2つのトークン配置んとゐ,および非負整数 \ell\geq 0 が与えられたとき,色付
きトークン整列問題とはdist (fo, f_{t})\leq\ell であるか判定する問題である.

3

スプリットグラフ
本節では,スプリットグラフのNP 完全性を示す.グラフ G の点集合 V(G) をクリークと独立点集合に分割できるとき,

G はスプリットグラフと呼ばれる.本節の主結果は,次の定理である.

定理1 スプリットグラフに対する色付きトークン整列問題は,色数 c を3以上の任意の定数に制限しても NP 完全である.

証明.Yamanaka ら [11] によって, n 頂点グラフ G の到達可能なトークン配置 f と f' に対し,dist (f, f^{\ovalbox{\t \small REJECT}})=O(n^{2}) であることが示されているため,本判定問題はクラスNP に属する.
したがって本稿では,3次元マッチング問題 [3] から本問題への多項式時間帰着を構成する
ことによってNP 困難性を示す.証明の基本的なアイディアは,Yamanaka らの平面二部グ

ラフに対する NP 困難性の証明 [11] と同じである.
3次元マッチング問題は,次のように定義される.

いに素な3つの集合 X, Y,のとき,|X|=|Y|=|Z|=m であるような互Z と,それらの直積の部分集合 S\subseteq X\cross YxZ が与えられる.こX, Y, Z のすべての要素がちょうど一度ずつ含まれるような,サイズ m の部分集合

57

f_{0} fi_{t}

図3: 3次元マッチング問題の問題例 X =\{x_{1}, x_{2}\},

Y=\{y_{1}, y2\}, Z=\{z_{1}, z_{2}\}, S=\{s_{1}=(x_{1}, y_{1}, z_{1}), s_{2}=(x_{1}, y2, z_{1}), s_{3}=(x_{2}, y_{1}, z_{2})\} に対応す

る色付きトークン整列問題の問題例.

\ell=3m=6 である.

S'\subseteq S が存在するかどうか判定する問題である.3次元マッチング問題は NP 完全であることが知られている [3].
3次元マッチング問題の問題例から,色付きトークン整列問題の対応する問題例を構成す

る.(図3参照.) 対応するグラフ G の頂点集合は 3m+|S| 個の頂点を持ち , X, Y, Z およびS の各要素に対応する.なお, V(G) の頂点部分集合および頂点を,3次元マッチング問題の集合および要素と同じ名前で呼ぶこととする. s_{i}=(x_{a}, y_{b}, z_{c})\in S であるとき, G において,対応する頂点 s_{\iota} と頂点 x_{a}, y_{b}, z 。をそれぞれ辺で結ぶ.また, S のすべての2頂点間を辺で結び,クリークを構成する.以上により,対応するスプリットグラフ G を得る.次に,G のトークン配置 f_{0} とゐを次のように定義する.各点

v\in V(G) に対し,

f_{0}(v)=\{begin{ar y}{l 1v\inSのとき; 1v\inXのとき; 2v\inYのとき; 3v\inZのとき， \end{ar y}f_{t}(v)=\{begin{ar y}{l 1v\inSのとき 2v\inXのとき; 3v\inYのとき; 1v\inZのとき． \end{ar y}

最後に,色付きトークン整列問題のトークン交換回数 (の上限) を \ell=3m と設定する.
3次元マッチング問題の与えられた問題例から,色付きトークン整列問題の対応する問題
例を構成することは,明らかに多項式時間でできる.この帰着の正当性の証明は,本稿では省略する.口4

完全二部グラフ
本節では,完全二部グラフに対し,色数 c に関する FPT アルゴリズムを与える.我々のアルゴリズムは,完全グラフに対する FPT アルゴリズム [11] のアイディアを拡張したものである.

まず,小節4.1では,どちらのグラフクラスに対しても使われる色グラフという概念を導入する.その後,小節4.2において,色グラフを用いた FPT アルゴリズムを与える.

58

図4: 図3のんとゐに対する色グラフ D(f_{0}, f_{t}) .

4.1

色グラフ

グラフ G のトークン配置 f と f' に対し,色グラフ D(f, f') とは次のように定義される有向グラフである.(図4参照.)\bullet\bulletD(f, f') の頂点集合は C である.ここで, C は色数 c の色集合である.
D(f, f') の有向辺集合を A(f, f') と書くと, A(f, f')=\{(f'(v), f(v))|v\in V(G)\} である.

したがって,色グラフの各頂点は C の色に対応しており,各有向辺は V(G) の頂点に対応している. f(v)=f'(v) である頂点 v\in V(G) は,色グラフでは自己ループに対応する.以降,色グラフとの混同を避けるために,入力で与えられるグラフ G を基グラフと呼ぶことがある.

基グラフ G のトークン配置 f と f' が与えられたとき,その色グラフ D(f, f') は,線形時間で求めることができる.したがって以降では,色グラフ D(f, f') も入力として与えられると仮定する.

4.2

FPT アルゴリズム

本小節では,はじめに次の定理を紹介する.

定理2 ([11])n頂点の完全グラフ G , 色数 c の G のトークン配置んと f_{t} が与えられたとき,dist (f_{0}, f_{t}) を g(c)\cdot n^{O(1)} 時間で計算するアルゴリズムが存在する.ここで, g は計算可能な関数である.

この証明のため,色グラフ D(f_{0}, ft) に対し,次の定義をする.
ルー プの集合を A_{se}1f(f_{0}, ft) と書き,

D (fo, ft) に含まれる自己\#self(fo, ft)=|A_{se}1f(f_{0}, ft)| とする.有向辺部分集合

A(f_{0}, ft)\backslash A_{e}1f(f_{0}, ft) を有向サイクルに分割したもののうち,有向サイクル数が最大となるものを考え,その際の有向サイクル数を #cycle (f_{0}, ft) とする.なお,そのような分割が存在しない場合には,#cycle (f_{0}, ft)=-\infty と定義する.このとき,次の補題1が成り立つが,その証明は省略する.

補題 1d1st(f_{0}, f_{t})=n- #self (f_{0}, f_{t})- #cycle (f_{0}, f_{t})
したがって,定理2を証明するには, \#\cdot elf(f_{0}, f_{t}) と \#_{c}y_{cle}(f_{0}, f_{t}) が所望の計算時間で求め\#_{self}(f_{0}, f_{t}) は線形時間で求められる.一 方で, \#_{cycle}(f_{0}, f_{t}) は,られればよい.明らかに,

次の補題に示すように,整数計画探索問題として定式化することで,所望の計算時間で求め
られる.

59
補題2色グラフ D(f_{0}, f_{t}) に対する \#_{cycle}(f_{0}, f_{t}) は,

証明.

\mathb {Z} を整数の集合とする.

d 個の変数,mc^{O(c^{c+1})}(\log n)^{O(1)} 時間で求められる.

個の制約式を持つ整数計画探索問題では,入力として行列 A\in \mathbb{Z}^{m\cross d}
Ax\leq b を満たすベクト
ル x\in \mathbb{Z}^{d\cross 1} が存在するか判定し,存在する場合にはそれを一つ出力する. A または b に現とベクト) \triangleright b\in \mathbb{Z}^{m\cross l} が与えられたとき,れる要素の最大値を \triangle とすると,この問題はd^{O(d)}m^{O(1)}(\log\triangle)^{O(1)}(1)

時間で解けることが知られている [5].
本稿では,整数 k に対し \#_{cycle} (f_{0}, f_{t})\geq k であるか判定する問題を,整数計画探索問題に定式化する.色グラフの有向辺集合は,基グラフの頂点集合に対応するから,ちょうど n
本の有向辺を持つ.したがって,\#_{cycle}(f_{0}, f_{t})\leq n である.これより,整数 k は 0,1,nの範囲を調べれば十分であり,二分探索を行うことで \#_{cyde}(f_{0}, f_{t}) を計算できる.

色グラフ D(f_{0}, f_{t}) の頂点集合 C に対し,長さ r の順序列を考える.その順序で頂点を辿る有c
向サイクルが D(f_{0}, f_{t}) に存在するとき,その順序列は適切であるという.長さ r=2,3,の適切な順序列を全て列挙し, \ovalbox{\tsmalREJCT} 番目に列挙された適切な 1頂序列が選択される回数を変数吻で表す.すると, \#_{cycle}(f_{0}, f_{t})\geq k という制約は,(2)x_{1}+x_{2}+\cdots+x_{d}\geq kという制約式で表現できる. D (fo, f_{t} ) は c 個の頂点を持つから,列挙される適切な順序列は高々 (c+1)^{c} 個である.したがって,変数の個数 d は, d\leq(c+1)^{c} と抑えられる.
一方で, D(f_{0}, f_{t}) の頂点集合 C の各順序対 i\in C\cross C に対し,その順序対を結ぶ A(f_{0}, f_{t})\backslash
A_{self}(f_{0}, f_{t}) の有向辺の本数を bi とする.所望の分割では,どの順序対 i\in C\cross C に対して
も,有向サイクルとして選ばれるのは高々 b_{i} 回でなければならない.この制約を表現するた
めに,整数計画探索問題の行列 A の各要素 a_{i_{j}} を次のように定義する.

a_{lj}=\{\begin{ar ay}{l} 1 j 番目の適切な順序列が，順序対 i を含むとき; 0 その他． \end{ar ay}

順序対 i\in C\cross C は c^{2} 個あるため,制約式 (2) と合わせて , 制約式の総数 m は m=c^{2}+1個である.また,A または b に現れる要素の最大値 \triangle は,\triangle\leq n と抑えられる.したがって,(1) より,この整数計画探索問題は((c+1)^{c})^{O((c+1)^{c})}(c^{2}+1)^{O(1)}(\log n)^{O(1)}時間で解け,補題を得る.口

詳細は省略するが,完全二部グラフに対しても dist (f_{0}, f_{t}) を色グラフ D(f_{0}, f_{t}) に含まれる有向サイクルの個数等を用いて特徴づけることができる.ただし,完全グラフとは異なり,完全二部グラフには辺で結ばれていない頂点対があるため,より詳細な特徴づけが必要となる.それら dist (f_{0}, f_{t}) の特徴づけに必要な値は,補題2のように整数計画探索問題に定式化することで求められ,本小節の主な結果として次の定理を得る.

定理3n頂点の完全二部グラフ G , 色数 c の G のトークン配置んとゐが与えられたとき,

dist (f_{0}, f_{t}) を g'(c)\cdot n^{O(1)} 時間で計算するアルゴリズムが存在する.ここで, g' は計算可能な関数である.

60\pm<

ロ \square\inftyロ(a)(b)

図5: (a) コグラフ G と (b) G の分解木.

5

コグラフ
本節では,コグラフに対し,色数 c に関する XP アルゴリズムを与える.

5.1

コグラフとその分解木

コグラフを再帰的に定義するため,まず2つのグラフの結合操作を定義する.グラフ G_{1}=(V_{1}, E_{1}) と G_{2}= ( V_{2} , E2) に対し,その和結合によって得られるグラフ G_{1}\cup G_{2} は,点集合
V(G_{1}\cup G_{2})=V_{1} 火巧であり,辺集合 E(G_{1}\cup G_{2})=E_{1}\cup E_{2} である.一方で, G_{1} と G2の積結合によって得られるグラフ G_{1}\vee G_{2} は,点集合 V (G_{1}V G2)=V_{1}\geq V_{2} であり,辺集合

E(G_{1}\vee G_{2})=E_{1}\cup E_{2}\cup\{vw|v\in V_{1}, w\in V_{2}\} である.コグラフは,次のように再帰的に定義される [2].
(a) 1つの頂点からなるグラフは,コグラフである.
(b) グラフ G_{1}=(V_{1}, E_{1}) と G2= ( V2, E2) がコグラフであるとき,その和結合によって得られるグラフ G_{1}\cup G_{2} はコグラフである.

(c) グラフ G_{1}=(V_{1}, E_{1}) と G2= (V2, E_{2}) がコグラフであるとき,その積結合によって得られるグラフ G_{1}\vee G_{2} はコグラフである.

コグラフ G は,図5に例示するように,その構造を分解木で表すことができる.すなわ
ち,分解木の各葉は G の各頂点に対応し,分解木の内部点は和結合または積結合を表す.本

稿では,コグラフの頂点との混同を避けるために,分解木の頂点をノードと呼ぶ.また,本
稿では連結グラフのみを考えるため,分解木の根は常に積結合となる.コグラフ G が与えられたとき,その分解木は線形時間で求められるため [8] , 本稿では分解木も与えられると仮定する.

コグラフ G の分解木の各ノード u に対し,

ドu

G の部分グラフを次のように対応させる.ノーを根とする部分木に含まれる葉に対応する G の頂点集合を隔と表す.ノード u には,

V_{u} から誘導される G の部分グラフ G_{u} が対応する.

5.2

コグラフのXP アルゴリズム

本節の主結果は,次の定理である.

定理4

頂点のコグラフ G , 色数 c の G のトークン配置 f_{0} とゐが与えられたとき,dist (f_{0}, f_{t})を O(n^{g^{\ovalbox{\t \smal REJECT}\prime}(c)} 時間で計算するアルゴリズムが存在する.ここで, g" は計算可能な関数である.
n

61
61
定理4の証明として,所望の計算時間で dist (f_{0}, f_{t}) を計算するアルゴリズムを与える.我々のアルゴリズムは,コグラフの分解木に基いた動的計画法である.
本稿のアルゴリズムでは,特定の辺集合に限定したトークンの交換を扱うため,次のような記法を導入する.あと乃を基グラフ G=(V, E) の任意のトークン配置とする. G の辺部
分集合 E'\subseteq E に対し,ゐから乃へのトークン交換系列 \{s_{1}, s2, . 8_{r}\} が,全ての 1\leq i\leq r
において s_{i}\in E' を満たすとき,その交換系列は E' に制限されたトークン交換系列と呼ばれる.あから f_{j} への E' に制限されたトークン交換系列のうち,最小の長さをdist (E';f_{i}, f_{j})と書く.ただし,そのようなトークン交換系列が存在しない場合にはdist (E';f_{i}, f_{j})=+\inftyとする.また,dist (f_{i}, fj)=dist(E;f_{i}, f_{\dot{j}}) であることに注意されたい.
コグラフ G の分解木の内部ノード u に対し,その2つの子を c_{1} とc2とする.また,それぞれのノードに対応する G の部分グラフを G_{u}=(V_{u}, E_{u}), G_{c_{1}}=(V_{1}, E_{1}) , G_{c_{2}}=(V_{2}, E_{2})とし, E_{12}=E_{u}\backslash (E_{1}\cup E_{2}) とする.したがって, u が和結合であれば E_{12}=\emptyset であり,積結合であれば E_{12} に誘導される G の部分グラフは巧と巧を頂点集合とする完全二部グラフである.我々は次の補題が成り立つことを示したが,本稿ではその証明を省略する.
補題3部分グラフ G_{u} の任意のトークン配置 f と f' に対し, f と f' への (E_{u} に制限された ) トークン交換系列には,次の条件 (i) と (ii) を満たす \mathcal{S}=\{s_{1}, s_{2},s_{r}\rangle が存在する.

(i) |\mathcal{S}|=dist(E_{u};f, f') .

(ii)

1\leq r_{1}\leq r_{2}\leq r なる整数 r_{1} と r_{2} に対し,以下の条件(a)-(c) を満たす.
(a) \{s_{1}, s_{2}\ldots, s_{r1}\rangle は, E_{1} に制限されたトークン交換系列である.
(b) \langle \mathcal{S}_{r_{1}+1}, S_{r_{1}+2}\ldots, \mathcal{S}_{r2}\} は, E_{2} に制限されたトークン交換系列である.
(c) \{s_{r_{2}+1}, s_{r_{2}+2}\ldots, s_{r}\rangle は, E_{12} に制限されたトークン交換系列である.

コグラフ G のトークン配置 f に対し,部分グラフ G_{u} へ f を制限したトークン配置を費と書く.すなわち, f^{u} は G_{u} のトークン配置であり,全ての点 v\in 覧に対し野(v) =f(v)を満たす.また, G_{c}1 と G_{c}2 のトークン配置 f_{1} と f2を組合わせて得られる G_{u} のトークン
配置を f_{1}\cup f_{2} と書くことにする.すると,補題3より,以下の式が成り立つ.

dist( E_{u};f_{0}^{u}, f_{t}^{u})=\min_{1f,f2}dist(E_{1};f_{0}^{c_{1}}, f_{1})+dist (E_{2};f_{0}^{c2}, f_{2})+dist(E_{12};f_{i}\cup f_{2}, f_{t}^{u}) .

(3)

ここで,式(3) の \min は, G_{c1} と G_{c}2 の全てのトークン配置 f_{1} と f_{2} に対して取られる. uが和結合であれば E_{12}=\emptyset であるから,dist (E_{12};fi\cup f_{2}, f_{t}^{u})=0 である.一方で, u が積結合であれば E_{12} に誘導される G の部分グラフは防と V_{2} を頂点集合とする完全二部グラ
フであるから,dist (E_{12};f_{l}\cup f2, f_{t}^{u}) は定理3のFPT アルゴリズムを用いて計算できる.しかしながら,式(3) では G_{c_{1}} と G_{c_{2}} の全てのトークン配置 f_{1} と f_{2} が \min の対象となることから,このままでは指数時間アルゴリズムである.我々は,トークン配置の “パターン“ を特徴づけることによって,実際には色数 c に対して O(n^{g"(c)}) 個のトークン配置を対象として\min を計算するだけで,正しくdist (f_{0}, f_{t}) が計算できることを示したが,本稿では省略

する.

6

まとめ
本稿では,色付きトークン整列問題に対し,色数 c をパラメータとした際のパラメータ複雑性を解析した.特に本稿では,図2に示すように,グラフクラスに基づいた解析を行った.

62
一方で,コグラフに対しては色数 c をパラメータとした FPT アルゴリズムが存在する可能性は残されており,完全二部グラフに対しては多項式時間で解ける可能性もある.これらを明らかにすることが,今後の課題として挙げられる.

参考文献[1] É. Bonnet, T. Miltzow and P. Rzazewski, Complexity of token swapping and its
variants. Proceedings of the 34th International Symposium on Theoretical Aspectsof Computer Science (STACS 2017), Leibniz International Proceedings in Informat‐
ics 66, pp. 16:1−16:14, 2017.

[2] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey. Society for
Industrial and Applied Mathematics, Philadelphia, PA, 1999.

[3] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theoryof NP‐Completeness. Freeman, San Francisco, CA, 1979.

[4] M.R. Jerrum, The complexity of finding minimum‐length generator sequence. Theo‐
retical Computer Science 36, pp. 265‐289, 1985.

[5] R. Kannan, Minkowski’s convex body theorem and integer programming. Mathe‐
matics of Operations Research 12, pp. 415‐440, 1987.

[6] J. Kawahara, T. Saitoh and R. Yoshinaka, The time complexity of the token swapping
problem and its parallel variants. Proceedings of the 11th International Conference

and Workshops on Algorithms and Computation (WALCOM 2017), Lecture Notes in
Computer Science 10167, pp. 448‐459, 2017.

[7] D.E. Knuth, The Art of Computer Programming, vol. 3, 2nd edition. Addison‐Wesley,
Redwood City, CA, 1998.

[8] R.M. McConnell and J.P. Spinrad, Linear‐time modular decomposition of directed
graphs. Discrete Applied Mathematics 145, pp. 198‐209, 2005.

[9] T. Miltzow, L. Narrins, Y. Okamoto, G. Rote, A. Thomas and T. Uno, Approx‐
imation, hardness of token swapping.

Proceedings of the 24th European Sympo‐

sium on Algorithms (ESA 2016), Leibniz International Proceedings in Informatics 57,
pp. 66:1−66:15, 2016.

[10] K. Yamanaka, E.D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T.
Saitoh, A. Suzuki, K. Uchizawa and T. Uno, Swapping labeled tokens on graphs.
Theoretical Computer Science 586, pp. 81‐94, 2015.

[11] K. Yamanaka, T. Horiyama, J.M. Keil, D. Kirkpatrick, Y. Otachi, T. Saitoh, R.
Uehara and Y. Uno, Swapping colored tokens on graphs.
Science, DOI: 10. 1016/j . tcs. 2018.03.016, in press.

Theoretical Computer