グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀

応用 －周波数帯域割当て －タスクスケジューリング 応用 －周波数帯域割当て －タスクスケジューリング 必要な帯域幅（MHｚ） 4 5 2 基地局間で干渉を起こさないために離す帯域幅（MHｚ） 4 2 3 7 2 1 10 11 1 連続した帯域を割り当てる 1 11MHｚ 3 4 5 6 使用帯域幅 10 1 2 3 4 5 6 7 8 9 10 11

帯域幅連続多重彩色( 彩色) 4 10 5 11 6 1 5 6 12 13 1 条件 3 7 6 8 12 自然数(色)集合 グラフ 帯域幅連続多重彩色(　彩色) 自然数(色)集合 4 10 5 11 6 1 5 6 グラフ 1 2 3 2 3 7 4 正整数 点重み 最大 12 13 非負整数 辺重み 1 条件 各点　　に連続した　　　個の 正整数(色)からなる集合 を割り当てる． 3 7 6 8 12 (2) 各辺　　　　について， 　　　 の色と　　　　の色は 　　　　　　　　以上離れている． ＝13 ＝11 の　彩色数 ＝11

帯域幅連続多重彩色問題 (　彩色問題) 入力: 　　－ グラフ 　　－ 重み関数 出力: 　　　最適な　彩色 最小

彩色 の簡単な表現 4 10 5 11 6 1 条件 各点 に連続した 個の 正整数(色)からなる集合 を割り当てる． (a) (b) 　　彩色　 の簡単な表現 4 10 5 11 6 1 1 2 3 2 3 7 4 条件 各点　　に連続した　　　個の 正整数(色)からなる集合 を割り当てる． (2) 各辺　　　　について， 　　　 の色と　　　　の色は 　　　　　　　　以上離れている． (a) (b) (c) for

既存研究 点彩色 : 1かつ 0なる 彩色 多重彩色 : 0なる 彩色 (ただし連続でなくてもよい) 帯域幅彩色 : 1なる 彩色 点彩色　　　 :　 　　　　 1かつ　　　　　　0なる　彩色 多重彩色 :　　　　　　　　0なる　彩色 　(ただし連続でなくてもよい)　　　　　　 帯域幅彩色 :　　　　　　 1なる　彩色 本文の帯域幅連続多重彩色(　彩色)は，これらの一般化

結果 P ? 本研究 木 NPC FPTAS O(n) FPTAS 部分3木 部分k木 直並列グラフ(部分2木) 一般のグラフ 点彩色 多重彩色 帯域幅彩色 ? FPTAS 帯域幅連続多重彩色 (b彩色) O(n) [AP’89] [ZN’04] [INZ’03] [MR’03] 擬多項式時間 厳密アルゴリズム FPTAS 本研究

直並列グラフの再帰的定義 直並列グラフ 1. 直並列グラフ（直列接続） 2. 直並列グラフ 直並列グラフ（並列接続）

なる　彩色　の最小スパン 10 8 2 1 2 1 ・ ・ ・ ・ ・ ・ 2 1 存在しない

直並列グラフ 普通の点彩色数 最大重み 補題1. だけを計算すればよい

厳密アルゴリズム 直並列グラフ 条件 (a) 満たす (b) 満たさない (c) for

時間計算量 並列接続 時間 直列接続 時間 の個数 の計算 直列接続または 並列接続の回数 が多項式ならば も多項式 直並列グラフ　　（並列接続） 直列接続 時間 直並列グラフ　　（直列接続） 　　　の個数 　　　の計算 直列接続または 並列接続の回数 が多項式ならば　　　　も多項式

FPTAS(Fully Polynomial-Time Approximation Scheme) 近似誤差率　　　　　　　　　　を任意に選択　 時間計算量 が直並列グラフならば 近似解:

FPTAS(Fully Polynomial-Time Approximation Scheme) 2 1 4 7 任意のグラフ 近似誤差率　　　　　　　　　　を任意に選択　 縮尺率　 を適切に決める 3 6 1 の最適解 正整数 1 2 4 重み 　　　　　　　なる 新しい重み 新しい最大重み 時間計算量 が直並列グラフならば の　彩色(近似解) 6 12 2 2 1 4 7 近似解

結論 P ? 本研究 木 NPC FPTAS O(n) FPTAS 部分3木 部分k木 直並列グラフ(部分2木) 一般のグラフ 点彩色 多重彩色 帯域幅彩色 ? FPTAS 帯域幅連続多重彩色 (b彩色) O(n) [AP’89] [ZN’04] [INZ’03] [MR’03] 擬多項式時間 厳密アルゴリズム FPTAS 本研究

今後の課題 時間計算量　　　　　　　　　　　　などの改善

参考文献 国際会議 K. Nishikawa, T. Nishizeki and X. Zhou, Algorithms for bandwidth consecutive multicolorings of graphs (Extended Abstract), Proc. FAW-AIIM 2012, Lecture Notes in Computer Science, Vol. 7285, pp.117-128, 2012.

2 1 3 7 4 2 1 3 7 4 1 2 4 1 2 4

一般のグラフ :定数 部分 -木 部分3-木 直並列グラフ (部分2-木) 木 :点数

　　彩色　 の簡単な表現 逆に が(a)(b)(c)を満たす が(1)(2) を満たす 条件 (a) (b) 同値 (c) for

　　彩色　 の簡単な表現 条件 (a) (b) (c) for

　　彩色　 の簡単な表現 (c) for 正 条件(2)を満たす

1．基本的な性質 補題1. どんな重み付きグラフ　 に対しても， 最大重み 普通の彩色数 1 2 3 色 の部分集合 証明. 独立 は　 彩色

1．基本的な性質 二部グラフや木に対しては線形時間で最適な 彩色が求まる 補題2. を二部グラフまたは木とし， とする．この時， 証明. 二部グラフや木に対しては線形時間で最適な　彩色が求まる 補題2. 　　　　　　　を二部グラフまたは木とし， とする．この時， は自明 を証明する 証明. 　 彩色 の部分集合 の部分集合

の証明 3 6 1 ：最適な　彩色， for の向き付け 2 1 は無閉路的 閉路があるならば 閉路はない

6 条件 3 1 の証明 なる無閉路的向き付け において へ行く最長有向道の長さ (a) (b) (c) 非負 正 2 1 2 2 2 1 の証明 なる無閉路的向き付け において　　へ行く最長有向道の長さ 6 (a) 条件 2 2 2 1 (b) 3 1 (c) のとき 非負 正

6 条件 3 1 の証明 なる無閉路的向き付け において へ行く最長有向道の長さ (a) (b) 非負 正 (c) 2 1 2 2 1 の証明 なる無閉路的向き付け において　　へ行く最長有向道の長さ 6 条件 2 (a) 2 1 (b) 3 1 非負 正 (c) のとき なので矛盾 逆向き

1．基本的な性質 ・ ・ ・ 補題3.どんな重み付きグラフ に対しても， 最長路 最長路 の無閉路向き付け の無閉路向き付け 有向道 の長さ 補題3.どんな重み付きグラフ　 に対しても， の無閉路向き付け の無閉路向き付け 最長路 ＝1+2+2+4+2＝11 有向道　　の長さ 有向道　　の長さ 2 1 3 7 4 2 1 3 7 4 2 1 3 7 4 2 1 3 7 4 ＝3+2+1+0+2＝8 ・ ・ ・ 最長有向道　　の長さ ＝3+2+1+7+1+0+1+7+2＝24 有向道　　の長さ 有向閉路 最長路 ＝11 最長有向道　　の長さ 無閉路向き付けではない 無閉路向き付け ＝24

1．基本的な性質 ・ ・ ・ ・ ・ ・ =11 補題3.どんな重み付きグラフ に対しても， 最長路 最長路 ＝24 ＝11 2 2 4 4 補題3.どんな重み付きグラフ　 に対しても， =11 最長路 2 1 3 7 4 2 1 3 7 4 ・ ・ ・ 最長路 ＝24 ・ ・ ・ ＝11

6 3 1 6 3 1 条件 の証明 ：最適な 彩色， の向き付け for は無閉路的 の最長有向道 道 (a) (a) (b) (c) 2 1 ：最適な　彩色， for の向き付け 3 6 1 2 1 は無閉路的 の最長有向道 道 条件 (a) (b) (c) for (a) (c) (c) (c) ・　 ・　 ・　 ・　 ・　 ・　 ・　 ・　 ・　 ・　 ・ (c)

6 3 1 の証明 なる無閉路的向き付け において へ行く最長有向道の長さ は条件(a)(b)(c)を満たすので， は 彩色 2 1 の証明 なる無閉路的向き付け において　　へ行く最長有向道の長さ 6 2 2 1 は条件(a)(b)(c)を満たすので， 3 1 は　　彩色 は最適とは限らない □

直並列グラフ 直並列グラフ 直並列グラフ 直並列グラフ（並列接続） 直並列グラフ（直列接続）

FPTAS(Fully Polynomial-Time Approximation Scheme) 任意のグラフ 2 1 4 7 近似誤差率　　　　　　　　　　を任意に選択　 3 6 1 の最適解 1 2 4 重み 　　　　　　　なる 縮尺率を適切に決める 6 12 2 の　彩色(近似解) 2 1 4 7 厳密アルゴリズムは　　と　　の多項式時間

条件 条件 (a) (b) for (c) (a) (b) (c) for 条件(a)(b)(c)より， は 彩色 は の 彩色 両辺に 2 は　　　の　　彩色 条件 (a) (b) for (c) 両辺に 2 1 4 7 両辺に 3 6 1 の最適解 1 2 4 重み 　　　　　　　なる 両辺に 条件 (a) 6 12 2 (b) の　彩色(近似解) 2 1 4 7 (c) for 条件(a)(b)(c)より，　　は　彩色

厳密アルゴリズム（直列接続） 直並列グラフ　　（直列接続） 時間

厳密アルゴリズム（並列接続） 直並列グラフ　　（並列接続） 時間

補題5. 任意のグラフ の任意の無閉路向き付け の最長路 任意の正整数 の重みが のグラフ と同じ向き付け の最長路 2 1 3 7 4 2 7 4 2 1 3 7 4 任意のグラフ の任意の無閉路向き付け の最長路 任意の正整数 　の重みが　　のグラフ と同じ向き付け の最長路 1 2 4 1 2 4

の証明 2 1 3 7 4 両辺に は最長 1 2 4 両辺を　 で割ると □

補題4. 任意のグラフ 近似解 最適解 証明． が最小になる　　の無閉路向き付け の最長路 誤差 　高々 補題３より 両辺に

上の式 誤差 高々 の最長路 誤差 高々 証明は省略するが 誤差 高々 補題3より 両辺に 最長路が最小になる の向き付け 両辺に 両辺に 　高々 の最長路 誤差 　高々 証明は省略するが 両辺に 誤差 　高々 補題3より 両辺に 両辺に 最長路が最小になる　　の向き付け □

補題4. 誤差 証明． 高々 が最小になる の無閉路向き付け の最長路 誤差 高々 誤差 高々 最長路長が最小になる の無閉路向き付け 任意のグラフ 誤差 　高々 近似解 最適解 証明． 誤差 　高々 が最小になる　　の無閉路向き付け の最長路 誤差 　高々 最長路長が最小になる　　の無閉路向き付け □

近似解

定理． グラフのクラス　 に対し，　彩色問題を，　と　 に関する多項式時間 で解く厳密アルゴリズムがあるならば，クラス　 に対してFPTASが存在する． 直並列グラフに対し，　彩色問題を　 と　 に関する多項式時間　　　　　　で解く厳密アルゴリズムがあるので， 系1． 直並列グラフの　彩色問題に対してFPTASが存在する． その時間計算量は 定理より，

グラフの帯域幅連続多重彩色( 彩色) 彩色の基本的な性質 直並列グラフに対する擬多項式時間厳密アルゴリズム グラフの帯域幅連続多重彩色(　彩色) 　彩色の基本的な性質 直並列グラフに対する擬多項式時間厳密アルゴリズム 直並列グラフに対する近似アルゴリズム，FPTAS 部分　-木への拡張 結論 : 点数 : 任意の誤差率

-木の再帰的定義 -木 1. 点からなる完全グラフは 木である． -木 点からなる完全グラフは　木である． -木 　-木 　 が　木であり，その　点が完全グラフを誘導するとき，新しい１点を追加し， それら　点と辺で結んで得られるグラフも　 木である． 2.

3-木 3-木 3-木 1. 点からなる完全グラフは 木である． が 木であり，その 点が完全グラフを誘導するとき，新しい１点を追加し， 点からなる完全グラフは　木である． 3-木 　 が　木であり，その　点が完全グラフを誘導するとき，新しい１点を追加し， それら　点と辺で結んで得られるグラフも　 木である． 2. 3-木

部分　-木 部分　 -木: -木の部分グラフ 3-木 部分3-木

分解木 分解木 部分3-木

分解木 分解木 ・ ・ ・ ・ ・ ・

部分　-木 端子が 　+1個 ・ ・ ・ 補題1. なる　彩色　の最小スパン だけを計算すればよい

時間計算量 接続 時間 擬多項式時間 厳密アルゴリズム 　　　　　　　の計算 　　　　　　　の個数 接続の回数

定理． グラフのクラス　 に対し，　彩色問題を，　と　 に関する多項式時間 で解く厳密アルゴリズムがあるならば，クラス　 に対してFPTASが存在する． 部分　-木に対し，　彩色問題を　 と　 に関する多項式時間　 で解く厳密アルゴリズムがあるので， 定理より， 系2． 部分　-木の　彩色問題に対してFPTASが存在する． その時間計算量は

アルゴリズム ・ ・ ・ ・ ・ ・

3-木 3-木 3-木 1. 点からなる完全グラフは 木である． が 木であり，その 点が完全グラフを誘導するとき，新しい１点を追加し， 点からなる完全グラフは　木である． 3-木 　 が　木であり，その　点が完全グラフを誘導するとき，新しい１点を追加し， それら　点と辺で結んで得られるグラフも　 木である． 2. 3-木