splitグラフ上の全域木混雑度問題に対する反復丸めを用いた近似アルゴリズム
8
0
0
全文
(2) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. ( 2 ) 次数が µH 以下の頂点が葉であるような H の最小混 雑木が存在する．. になっている．k の最小化には，実行可能性について k に 関するバイナリサーチを行う．各制約式の説明を加える．. split グラフの最小混雑木に対して，次の補題が成り立つ．. (1) 式は辺 cngG,T ({u, v}) ≤ k を表す制約式である．ここ. 補題 2.2. 任意の split グラフ G に対して，任意の i ∈ I が. では k に x{u,v} をかけて条件を厳しくしている．(2) 式は. 葉であるような最小混雑木が存在する．. {u, v} 上を流れる s, t 間のフローは x{u,v} 以下であること. この補題から，今後 split グラフの最小混雑木では任意. を表している．(3) 式は各ソースから出るフローの合計は. の i ∈ I は葉であると仮定する．G の最小混雑木を T とす. 1 であり，各シンクに入るフローの合計も 1 であることを. る．e ∈ T と v ∈ Le (T ) に対して，Ne (v) = N (v) ∩ Re (T ). 表している．(4) 式はフロー保存則を表している．(5) 式は. とする．v ∈ Re (T ) のときも同様である．各 v ′ ∈ Ne (v) に. ソースに入るフロー，シンクから出るフローは 0 であるこ. 対して，{v, v ′ } の迂回路が e を通るため，|Ne (v)| は v の. とを表している．(6) 式は全域木制約である．各辺の端点. e の混雑度への寄与分と見ることができる．. からもう一方の端点へ 1 のフローを流さなければならない ので連結性もたもたれている．(7) 式の整数条件を除くこ. 3. IP 定式化と LP 緩和. とで LP 緩和が得られる．今後 IP を LP 緩和したものを. この章では split グラフ上の全域木混雑度問題を多品種. LP と表記する．. フローの容量最大値最小化問題を使った整数計画問題とし ての定式化を述べる．グラフ G = (V, E) を入力とし，T を. G の全域木とする．各辺 {s, t} ∈ E (G) をフローのソース. 3.1 split グラフ上の全域木混雑度の性質 split グラフ上の全域木混雑度の性質を述べ，その性質を. とシンクの組とみなし，s から t に 1 の整数フローを流す．. 定式化し，LP の制約式に加える．. ただし，フローを流すことができるのは T の辺のみであ. 補題 3.1. G を split グラフとする．このとき，次の条件を. る．s から t へのフローの流れが {s, t} の迂回路に対応す. 満たす全域木 T ∗ が存在する．. る．cngG (T ) = k であるかを調べるには，T の各辺の容量. ( 1 ) 任意の u ∈ I に対し，u が葉．. を k に設定し，フローを流すことができるかを調べればよ. ( 2 ) cngG (T ∗ ) = stc(G)．. い．このことを踏まえて，全域木混雑度問題を以下のよう に整数計画問題として定式化する．x{u,v} は辺 {u, v} ∈ T ならば 1，それ以外なら 0 となる変数である．f{s,t} (u, v) は {u, v} ∈ E (G) に対して，u から v へ流れる s, t 間のフ ローを表す．. 証明.. G の全域木 T ′ を cngG (T ′ ) = stc(G) であり，葉で. ないような u ∈ I が存在するような木とする．u の T ′ で の隣接点を v1 , v2 , . . . , vh とする．h は u の T ′ での隣接点 の個数である．T ′ から条件 1,2 を満たすような木 T ∗ を構 成する．. minimize. k. ま ず {u, v2 }, {u, v3 }, . . . , {u, vh } を T ′ か ら 除 き ，. (IP). subject to. ∑ {fs,t (u, v) + fs,t (v, u)} ≤ kx{u,v}. {v1 , v2 }, {v1 , v3 }, . . . , {v1 , vh } を 加 え る ．こ の と き 各 ∀{u, v} ∈ E,. {s,t}∈E. (1) fs,t (u, v) + fs,t (v, u) ≤ x{u,v} ∑ w∈N (s). ∑ w∈N (v). fs,t (w, t) = 1. ∀s ∈ V , (3). w∈N (t). は，µG ≥ |C| である．u の次数は高々 |C| なので，定理. 2.1 より，cngT ∗ ({u, v1 }) ≤ |C| ≤ stc(G) を得る．. fs,t (w, v) 補題 3.1 より，split グラフ上の全域木混雑度問題の最適. ∀v ∈ V \ {s, t}, ∀{s, t} ∈ E,. (4). 解では任意の u ∈ I は葉であると仮定できる．葉から出て. ∀{s, t} ∈ E, w ∈ V , (5). いる辺は 1 本のみであり，この辺の混雑度は葉の次数であ. (6). る．よって LP に次の 2 式を加える．. ∑. e∈E. xe , fs,t (u, v) ∈ {0, 1}. とを示す．次数が 2 以上の u ∈ I を持つ split グラフ G で. この操作を繰り返し行うことで，条件 1,2 を満たすような. w∈N (v). fs,t (w, s) = fs,t (t, w) = 0 ∑ xe = |V | − 1,. 立ち，カットされる辺の集合が等しいためである．. 全域木 T ∗ を構成できる．. ∑. fs,t (v, w) =. が成り立つ．なぜなら L{u,vi } (T ′ ) = L{v1 ,vi } (T ∗ ) が成り この操作により cngT ∗ ({u, v1 }) ≤ stc(G) が保存されるこ. ∀{s, t}, {u, v} ∈ E, (2). ∑. fs,t (s, w) =. i(2 ≤ i ≤ h) に対して，cngT ′ ({u, vi }) = cngT ∗ ({v1 , vi }). ∀e, {s, t}, {u, v} ∈ E.. (7). この定式化において，k を (整数に) 固定すると，目的関. {fi,t (i, v) + fi,t (v, i)} ≤ deg(i)x{i,v}. t∈N (i). ∀i ∈ I, ∀v ∈ N (i),. (8). 数のない線形制約整数計画問題の実行可能性を問う問題. c 2014 Information Processing Society of Japan ⃝. 2.
(3) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. ∑. x{i,v} = 1. ∀i ∈ I,. (9). v∈N (i). 今後，(8),(9) 式を加えた LP を LP–split と表記する．. 4. 乱択 2 近似アルゴリズム 4.1 アルゴリズム. この実行可能解を (x, f ) とし，{a, b} ∈ E ∩ T とする．各. i ∈ I に対して， ∑ j∈N (i) {fi,j (a, b) + fi,j (b, a)} ∑ ∗ ∗ ≤ 2 j∈N (i) {fi,j (a, b) + fi,j (b, a)}. j ∈ N (i) は任意とする．i ∈ I をソース，j をシンク. 証明.. としたとき，(3) 式より，i から j へ 1 のフローを流している．. Algorithm1 に 本 章 の ア ル ゴ リ ズ ム を ま と め て い る ． k ∗ = tc(G) とする．split グラフ G と k を入力とする. (2) 式より，任意の m ∈ N (i) に対して fi,j (i, m) ≤ x{i,m} が成り立つ．(x, f ) が LP の実行可能解ならば，任意の. LP を LP(G, k) と表記する．アルゴリズムでは最小混雑木. m ∈ N (i) に対してこの不等式が等号で成り立つことを. からクリーク内の部分木を得ている．その後，一部の変数. あり，クリークなのでこの部分木は G の辺から構成されて. 背理法で示す．fi,j (i, m′ ) < x{i,m′ } となる m′ ∈ N (i) が ∑ 存在すると仮定する．(3) 式より w∈N (i) fi,j (i, w) = 1 ∑ である．一方 (9) 式より w∈N (i) x{i,w} = 1 であるた ∑ ∑ め w∈N (i) fi,j (i, w) = w∈N (i) x{i,w} が成り立つ．仮. いる．よって，I の頂点を G の辺で接続されるように付け. 定より fi,j (i, m′ ) < x{i,m′ } となる m′ が存在するので，. 替えれば G の全域木を得ることができる．次節で次の定理. fi,j (i, m∗ ) > x{i,m∗ } と な る m∗ ∈ N (i)(m∗ ̸= m′ ) が. を示す．. 存 在 す る ．こ れ は (2) 式 に 矛 盾 す る ．以 上 か ら 任 意 の. 定理 4.1. Algorithm 1 の出力する木の混雑度を確率変数. m ∈ N (i) に対して fi,j (i, m′ ) = x{i,m′ } が成り立つ．任意. が決定された LP を解き，その解に基づいてランダムに解 を構成する．補題 3.1 から，クリーク内の部分木は連結で. Z であらわす．このとき，E[Z] ≤ 2stc(G)． Algorithm 1 Randomized Algorithm for STC on split 1: G の最小混雑木 T を求める． 2: 任意の e ∈ E ∩ T に対して，xe = 1 として LP(G, 2k∗ ) を解く． 3: for i ∈ I do 4: i の T での隣接点を u とする． 5: 確率 x{i,v} で {i, v} を選び，T := T ∪ {{i, v}} \ {{i, u}} に 更新する． 6: end for 7: return T. の j ′ ∈ N (i) をシンクとしたときも同様のことが言えるの で，各 {i, m} ∈ E について，. ∑. fi,j (i, m) = deg(i)x{i,m}. (10). j∈N (i). が成り立つ．(8),(10) 式より，i 以外の i′ ∈ I から流れるフ ローは i を経由せず，T ∩ G の辺上を流れる．よって i′ ̸= i を満たす i′ ∈ I についても各 j ′ ∈ N (i′ ) に対して，x{i′ ,j ′ } を固定すれば i と独立に同様の議論ができる．. Ne (i) が空でないような辺 e = {a, b} を考える．j ∈ Ne (i) をシンクとするとき，Ne (i) を経由して流れるフローは e を. 4.2 解析 G′ = G ∪ T とする．明らかに T は G′ の全域木である． また，加えた辺は I から出ている辺のみであり，さらに I の頂点は葉であるため，辺を加えたことによる混雑度の 増加は加えた辺に対してしか発生しない．i ∈ I から出て いる辺の混雑度は deg(i) ≤ |C| ≤ tc(G) である．よって. k ∗ = tc(G) とすると，T は LP(G′ , k ∗ ) の実行可能解であ る．この解を (x∗ , f ∗ ) で表す．ただし x∗ は { 1 (e ∈ T ) ∗ xe = 0 (e ∈ / T) とし，f ∗ は 0/1 解とする．以上の議論を観察としてまと めておく． 観察 4.2. (x∗ , f ∗ ) は LP(G′ , k ∗ ) の実行可能解である． ∗. ∗. ∗. (x , f ) から LP(G, 2k ) の小数実行可能解を構成する． 次の補題は k ′ を LP(G, k ′ ) が実行可能であるように選んだ ときの，小数実行可能解の性質に関するものである．この 補題から LP(G, 2k ∗ ) に実行可能解が存在することを示す． ′. 補題 4.3. k を，任意の e ∈ E ∩ T に対して，xe = 1 とし たときの LP(G, k ′ ) が実行可能解を持つような整数とする．. c 2014 Information Processing Society of Japan ⃝. 通らない．それ以外の N (i) の点を経由して流れるフロー は全て e を通る．よって，e を流れるフローの合計は. ∑. 1−. x{i,v}. (11). v∈Ne (i). である．j ∈ N (i) \ Ne (i) をシンクとするとき，Ne (i) の点 を経由するフローのみが e を通る．よって，e を流れるフ ローの合計は. ∑. (12). x{i,v}. v∈Ne (i). 以上から，. ∑. {fi,j (a, b) + fi,j (b, a)}. j∈N (i). = |Ne (i)|(1 −. ∑. x{i,v} ) + (deg(i) − |Ne (i)|). v∈Ne (i). = |Ne (i)| + (deg(i) − 2|Ne (i)|). ∑. ∑. x{i,v}. v∈Ne (i). x{i,v}. (13). v∈Ne (i). が成り立つ．ここで解の一つとして各 j ∈ N (i) に対して. 3.
(4) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report 1 deg(i). x{i,j} =. と置くと，(13) 式は. |Ne (i)| + (deg(i) − 2|Ne (i)|). む E(I) の迂回路の本数を YeI =. ∑. x{i,v}. v∈Ne (i). = |Ne (i)| + (deg(i) − 2|Ne (i)|). |Ne (i)| deg(i). て {a, b} を通るので， ∑ ∗ ∗ j∈N (i) {fi,j (a, b) + fi,j (b, a)} = |N{a,b} (i)| である．よっ て. |Ne (i)| |Ne (i)| + (deg(i) − 2|Ne (i)|) deg(i) ∑ ∗ ∗ ≤2 {fi,j (a, b) + fi,j (b, a)} j∈N (i). Ne (i) が空のときは I から流れるフローが e を通ることは ないので，. ∑. We. と. {i,j} j∈N (i) We. Ne (i) ̸= ∅ のときを考える．j ∈ Ne (i), j ′ ∈ N (i) \ Ne (i) と する．全域木の辺として {i, j} が選ばれたとき，各 {i, j ′ }. ∑. We{i,h} = deg(i) − |Ne (i)|. h∈N (i). となる．{i, j ′ } が全域木の辺として選ばれたとすると，. {i, j} の迂回路が e を通るので， ∑. We{i,h} = |Ne (i)|. h∈N (i). となる．よって， ∑ We{i,h} E h∈N (i). ∑. = (deg(i) − |Ne (i)|). {fi,j (u, v) + fi,j (v, u)}. j∈N (i). ∑. {i,j}. j∈N (i). する．ある i ∈ I と e = {a, b} を固定し， ∑ {i,j} を考える．Ne (i) = ∅ のとき j∈N (i) We = 0 である．. (x∗ , f ∗ ) において，j から N{a,b} (i) の頂点への迂回路は全. =. ∑ i∈I. の迂回路が e を通るので，. ≤ 2|Ne (i)|. ∑. ∑. + (1 −. ∗ ∗ {fi,j (u, v) + fi,j (v, u)} = 0.. j∈N (i). =. x{i,h}. h∈Ne (i). ∑. x{i,h} )|Ne (i)|. h∈Ne (i). ∑. {fi,h (a, b) + fi,h (b, a)}.. ((13) より) (14). h∈N (i). 補題 4.3 から直ちに次の補題が導ける． 補題 4.4. LP(G, 2k ∗ ) に対して，実行可能解が存在する．. S ⊆ V に対して，E(S) で S によって誘導される辺. 証明.. 集合とする．T ∩ G の各辺 e = {u, v} に対して，. ∑. {fs,t (u, v) + fs,t (v, u)}. i′ ∈ I(i′ ̸= i) から出るフローが i を経由することはないの で，I の点から辺を選ぶ操作は独立である．よって (14) 式 は任意の I の点に対して成り立つ．よって， ∑ ∑ E[YeI ] = E We{i,h} i∈I. {s,t}∈E. ∑. =. =. {fs,t (u, v) + fs,t (v, u)}. +. {fi,h (a, b) + fi,h (b, a)}. i∈I h∈N (i). {s,t}∈E(C). ∑ ∑. h∈N (i). ∑ ∑. ≤2. {fi,j (u, v) + fi,j (v, u)}. ∑ ∑. ∗ ∗ {fi,h (a, b) + fi,h (b, a)}.. (補題 4.3 より). i∈I h∈N (i). i∈I j∈N (i). ∑. ≤. ∗ ∗ {fs,t (u, v) + fs,t (v, u)}. {s,t}∈E(C). +2. ∑ ∑. ∗ ∗ {fi,j (u, v) + fi,j (v, u)}. (補題 4.3 より). 以上から任意の e ∈ T ′ に対して， ∑ g We E[Ye ] = E g∈E. i∈I j∈N (i). ≤2. ∑. . ∗ ∗ {fs,t (u, v) + fs,t (v, u)}. = E. {s,t}∈E. ∑. Weg + YeI . g∈E(C). ≤ 2k ∗ .. ((1) 式より). ≤. ∑. ∗ ∗ {fs,t (u, v) + fs,t (v, u)}. g∈E(C). 定理 4.1 の証明.. 各 e ∈ T ′ , g ∈ E に対して，Weg を g の. 迂回路に e が含まれているなら 1，そうでないなら 0 とな. +2. ∑ ∑. ∗ ∗ {fi,h (a, b) + fi,h (b, a)}. i∈I h∈N (i). ≤ 2k ∗ .. る確率変数とする．e を含む迂回路の本数，すなわち混雑 ∑ 度を Ye = g∈E Weg とする．E(C) の迂回路はすでに決定. が 成 り 立 つ ．k ∗ = tc(G) ≤ stc(G) よ り ，E[Z] =. されているので，E(I) の迂回路について見ていく．e を含. E[maxe∈T Ye ] ≤ 2stc(G).. c 2014 Information Processing Society of Japan ⃝. 4.
(5) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. 定理 4.1 では期待値が高々 tc(G) の 2 倍以内に収まるこ. 証明.. 任 意 の u ∈ I と 任 意 の v ∈ N (u) に 対 し て ， 1 deg(u). としか示していない．次章で本章のアルゴリズムの脱乱択. x{u,v} =. と置く．この解が LP–split2 の実行可能. 化を目指し，反復丸めアルゴリズムを用いた近似アルゴリ. 解であることを示す．明らかに，任意の f ∈ F に対して. ズムを与える．. (18) 式を満たす．任意の u ∈ I に対して ∑. 5. 反復丸めを用いた近似アルゴリズム. x{u,v} = deg(u). v∈N (u). この章では 4 章のアルゴリズムの脱乱択化を目指して，. =1. 決定的アルゴリズムを設計する．本章のアルゴリズムとそ の解析は [2] を参考にしている．. G の最小混雑木を T とする．アルゴリズムの方針は 4 章と. となるので (16) 式を満たす．また任意の e ∈ CIN に対して. ∑. 同じで，T からクリーク内の部分木を決定したあと，全域. ∑. 木を得るために I の頂点を G の辺で接続されるように付. u∈IRe (T ) v∈Ne (u). け替える．クリーク内の部分木を T (C) とする．T (C) の. +. ∑. の枝の集合を CIN とする．本章のアルゴリズムでは付け 替える際に生じる問題を線形計画問題として定式化し，反 である．. =. 付け替えが行われる際の e ∈ T (C) の混雑度の変化につい. =. v ∈ CRe (T ) の点へ付け替えられたとき，u の e への寄与 |Ne (u)| だったので，付け替えたことによる寄与分の増加 は deg(u) − 2|Ne (u)| である．u が CLe (T ) の点へ付け替え られたとき，u の e への寄与分は T のときと変わらない． ここで生じる問題は，全域木に作り変える際，各辺の混雑 度が 4 章で導出した期待値を超えないように I の頂点を 付け替えることである．この問題を以下のように定式化し た．任意の u ∈ I と v ∈ N (u) に対して，x{u,v} を {u, v} が全域木の辺となるなら 1，そうでないなら 0 をとる変数 ∑ とする．各 e ∈ T (C) に対して，Be = u∈I |Ne (u)| とす る．端点の一方が C に属しており，もう一方が I に属して いるような辺の集合を F とする．. minimize. 0. v∈N (u). ∑. ∑. ∀u ∈ I,. |Ne (u)| +. ∑. u∈ILe (T ) v∈Ne (u). ∑. |Ne (u)|. u∈IRe (T ). |Ne (u)| = Be. u∈I. となるので (17) も満たす． 一般的な線形計画問題に対して成り立つ次の補題を導入 する． 補題 5.2. 制約式の本数が m，変数の個数が n であるよう な線形計画問題の実行可能解を z とする．z が端点解であ るための必要十分条件は n 本の線形独立な制約式を等式で 満たすことである． 補題 5.2 から，今後の議論で重要な LP の端点解の性質 に関する補題を導くことができる． 補題 5.3. x を全ての要素が非零な LP–split2 の端点解と ∗ する．CL∗ , CIN をそれぞれ (17) 式を等号でみたす葉から. でている枝の集合と，それ以外の枝の集合とする．このと ∗ き，|F | = |I| + |CL∗ | + |CIN |．. (LP–split2). subIect to. ∑ x{u,v} = 1. ∑ u∈ILe (T ). て考察する．u ∈ ILe (T ) としても一般性を失わない．u が 分は deg(u) − |Ne (u)| となる．T での u の e への寄与分は. ∑. u∈IRe (T ) v∈Ne (u). 復丸めアルゴリズムを適用することで 2α + 2 近似アルゴ |C|−1 |CL | ⌉. deg(u) − 2|Ne (u)| deg(u). deg(u) − 2|Ne (u)| deg(u) u∈ILe (T ) v∈Ne (u) ∑ ∑ ∑ ∑ ≤ 1+ 1. 枝で，葉から出ているものの集合を CL ，それ以外の T (C). リズムを得る．ただし α = ⌈. 1 deg(u). 補題 5.2 から，x が端点解であるとき，|F | 本の制約. (15). 証明.. (16). 式を等号で満たしている．任意の f ∈ F に対して xf > 0 ∗ なので，等号を満たしている制約式は |I| + |CL∗ | + |CIN |本. (deg(u) − 2|Ne (u)|)x{u,v}. ∗ のみである．よって |F | = |I| + |CL∗ | + |CIN |．. u∈IRe (T ) v∈Ne (u)∩CLe (T ). +. ∑. ∑. (deg(u) − 2|Ne (u)|)x{u,v}. u∈ILe (T ) v∈Ne (u)∩CRe (T ). ≤ Be xf ≥ 0. ∀e ∈ T (C), ∀f ∈ F .. 5.1 反復丸めアルゴリズム Algorithm2 に 反 復 丸 め ア ル ゴ リ ズ ム を 載 せ る ．. (17). degF (v), NF (v) で辺集合が F のときの v の次数と，v の. (18). 隣接点の集合を表す．アルゴリズムでは，各反復の最初に. LP–split2 を解き，この LP 解に整数変数があるならばそ この定式化では期待値以内の解を見つけることに重点を置. れを解の一部に採用する．整数辺が無い場合は T (C) の葉. いているため，目的関数は特に定めない．. に 2α 個の I ′ の点が F ′ の辺で接続されていることが保証. 補題 5.1. LP–split2 は実行可能解を持つ．. される (補題 5.6) ため，それらの辺を全て解として採用す. c 2014 Information Processing Society of Japan ⃝. 5.
(6) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. 右辺に足し，実行可能性を保つようにする．このアルゴリ. 全ての v ∈ CL に対して，degF (v) > 2α と仮定し， ∑ 矛盾を導く．各 u ∈ I に対して， v∈N (u) x{u,v} = 1 であ. ズムに対して，次の補題が成り立つ．次節で証明する．. り，仮定から xf = 1 となる変数は存在しない．よって各. る．途中，制約式を違反した場合，違反分をその制約式の. ∗. 補題 5.4. e ∈ T (C) は任意とする．x をアルゴリズムか. 証明.. u ∈ I に対して. ら得られた LP–split2 の整数解とする．このとき，. ∑. ∑. (deg(u) − 2|Ne (u)|)x∗{u,v}. u∈IRe (T ) v∈Ne (u). ∑. +. ∑. (deg(u) − 2|Ne (u)|)x∗{u,v}. u∈ILe (T ) v∈Ne (u). ≤ Be + (2α + 1)|CRe (T ) ||CLe (T ) |. この補題から，ただちに次の定理を得る． 定理 5.5. 任意の split グラフに対して，stc(G) ≤ (2α +. 2)tc(G)． 証明.. 任 意 の e ∈ T ′ (C) に つ い て ，cngT (e) = Be +. |CRe (T ) ||CLe (T ) | である．定理 5.4 より， stc(G) ≤ cngT ′ (e). degF (u) ≥ 2. (19). ∗ が成り立つ．補題 5.3 より，|F | = |I| + |CL∗ | + |CIN | が成. り立つ．よって ∗ |I| + |CL∗ | + |CIN |. = |F | ∑ ∑ u∈I degF (u) + v∈C degF (v) = 2 ∑ v∈C\CL degF (v) > |I| + |CL |α + 2. (握手補題より). ≥ |I| + |C| − 1 ≥ |I| + |CL | + |CIN | ∗ ≥ |I| + |CL∗ | + |CIN |. ≤ cngT (e) + Be + (2α + 1)|CRe (T ) ||CLe (T ) | = 2Be + (2α + 2)|CRe (T ) ||CLe (T ) | ≤ (2α + 2)cngT (e) ≤ (2α + 2)tc(G).. となり，矛盾． この補題から，整数変数が存在しないときはアルゴリズ ムの 8 行目の処理に入ることが保証される．よって各反復 の開始前に比べて開始後は必ず入力のサイズが真に小さく なっている．このことから任意の split グラフに対してア ルゴリズムは停止する．定理 5.4 の証明に入る前に次の補. Algorithm 2 Iterative Algorithm for STC on split. 題を証明する．. 1: G の最小混雑木 T を求める． 2: T ′ := T (C), I ′ := I, F ′ := F, C ′ := C 3: while I ′ ̸= ∅ do 4: G′ = (C ∪ I ′ , F ′ ) 上で LP–split2 を解く． 5: 各 xf = 0 となる辺を全て除く． 6: 各 u ∈ I ′ と v ∈ N (u) に対して，x{u,v} = 1 ならば T ′ := T ′ ∪ {u, v}, I ′ := I ′ \ {u}, 混雑度が増加する全ての辺 e に対して， Be := Be − (deg(u) − 2|Ne (u)|) に更新． ′ を全て除く． 7: degF ′ (v) = 0 であるような v ∈ I ′ ∩ CL ′ に対して，degF ′ (v) ≤ 2α ならば 8: 各 v ∈ CL I ′ := I ′ \ NF ′ (v), C ′ := C ′ \ {v}, T ′ に v から出ている F ′ の辺を全て加える． 制約を違反した辺に対して，超過分を対応する制約式の右辺に 足す． 9: end while 10: return T ′. 補題 5.7. Algorithm2 の最初の反復において，7 行目の終 了時点で |I ′ | ≤ |C| − 1 が成り立つ． 証明.. 最初の反復での LP–split2 の端点解を x1 とする．. 変数の数は |F | 個，制約式の数は |I| + |C| − 1 本なので， 補題 5.2 より，少なくとも |F | − |I| − |C| + 1 個の x1 の 要素の値が 0 である．|I| > |C| − 1 のとき，Iβ を小数 辺の端点であるような I の頂点の集合とし，Iγ を整数辺. (xf = 1) の端点であるような I の頂点の集合とする．各 u ∈ Iβ は (16) 式より，少なくとも 2 本の辺を持つ．各 u ∈ Iγ はちょうど１本の辺を持つ．|Iβ | + |Iγ | = |I| かつ |I| + |C| − 1 ≥ 2|Iβ | + |Iγ | なので，|Iγ | ≥ |I| − |C| + 1 が 成り立つ．Iγ は全てアルゴリズムの 4 行目で除かれるた め，|I ′ | = |I| − |Iγ | ≤ |C| − 1． 補題 5.4 の証明. e ∈ T (C) は任意とする．一般性を失わ. 5.2 アルゴリズムの解析 この章では Algorithm2 の解析を行う．まず，アルゴリ. ず |CRe (T ) | ≤ |CLe (T ) | とする．アルゴリズムの 6 行目では 制約式を破ることはないので，6 行目の操作による混雑度. ズムの停止性を保障する次の補題を示す．. の増加は高々 Be である．. 補題 5.6. x を全ての要素が小数値であるような LP–split2. 8 行目のときの混雑度の増加を考える．u ∈ ILe (T ) とする．. の端点解とする．このとき，degF (v) ≤ 2α となるような. アルゴリズムによって u が CRe (T ) の頂点に付け替えられ. 頂点 v ∈ CL が存在する．. たとする．このとき，. c 2014 Information Processing Society of Japan ⃝. 6.
(7) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. うに付け替える．スターの場合の I の付け替えの問題を定. deg(u) − 2|Ne (u)| = |N (u) ∩ CLe (T ) |. 式化する．T がスターのとき，各 u ∈ I の e = {v1 , v} への. + |N (u) ∩ CRe (T ) | − 2|Ne (u)| = |N (u) ∩ CLe (T ) | + |Ne (u)| − 2|Ne (u)| ≤ |CLe (T ) | − |Ne (u)| ≤ |CLe (T ) |. よって e の混雑度は高々 |CLe (T ) | 増加する．u ∈. ′ IR e (T ). の. ときも同様である．8 行目での e の混雑度の増加の総和 は高々. ∑ ′ u∈IL. |CLe (T ) | +. ∑. である．よって Be =. ∑ u∈I. (23). |Ne (u)| = |N (v) ∩ I| である．. e の混雑度は v に I の頂点が付け替えられるとき，またそ のときに限り高々 deg(u) − 2 増加する．T がスターのとき の定式化は以下の通りである．. |CRe (T ) |. minimize. ′ u∈IR. e (T ). 寄与分 |Ne (u)| は { 1 (v ∈ N (u)) |Ne (u)| = 0 (v ∈ / N (u)). e (T ). 0. (LP–split2–star). subIect to ∑ x{u,v} = 1. ′ = |IL′ e (T ) ||CLe (T ) | + |IR ||CRe (T ) | e (T ). である．8 行目ではクリークの頂点１個につき高々 2α 個 の独立集合の頂点が接続されるので，. ∀u ∈ I, (24). v∈N (u). ∑. (deg(u) − 2)x{u,v} ≤ B{v,v1 }. ∀v ∈ C \ {v1 },. u∈I ′ |IR | ≤ 2α|CLe (T ) |, e (T ). (20). |IL′ e (T ) |. (21). ≤ 2α|CRe (T ) |. が成り立つ．補題 5.7 から， ′ |IR | + |IL′ e (T ) | ≤ |C| e (T ). (25) xf ≥ 0. ∀f ∈ F . (26). 次の補題が成り立つ．. (22). 補題 5.9. x を全ての要素が非零な LP–split2–star の端点 解とする．C ∗ を (25) を等号でみたす枝の集合とする．こ のとき，|F | = |I| + |C ∗ |．. である．以上から， ′ |IL′ e (T ) ||CLe (T ) | + |IR ||CRe (T ) | e (T ). ≤ |IL′ e (T ) ||CLe (T ) | + (|C| − |IL′ e (T ) |)|CRe (T ) |. 証明.. 補題 5.3 と同様．. Algorithm3 に本節のアルゴリズムを載せている．アル. ((22) 式より) =. |IL′ e (T ) |(|CLe (T ) |. − |CRe (T ) |) + |C||CRe (T ) |. ≤ 2α|CRe (T ) |(|CLe (T ) | − |CRe (T ) |) + |C||CRe (T ) | ((21) 式より) = (2α + 1)|CLe (T ) ||CRe (T ) | − (2α − 1)(|CRe (T ) |)2 ≤ (2α + 1)|CLe (T ) ||CRe (T ) |. 最 後 か ら 2 番 目 の 等 号 は |C| = |CRe (T ) | + |CLe (T ) | か ら 導 か れ る ．以 上 の 議 論 か ら ，8 行 目 で e の 混 雑 度 は 高々 (2α + 1)|CRe (T ) ||CLe (T ) | だけ増加する．よってア ルゴリズム全体での e の混雑度の増加は高々 Be + (2α +. 1)|CRe (T ) ||CLe (T ) |．. Algorithm 3 Iterative Algorithm for STC on split(star) 1: v1 を中心とするスターを構成する． 2: T ′ := T (C), I ′ := I, F ′ := F, C ′ := C 3: while I ′ ̸= ∅ do 4: G′ = (C ′ ∪ I ′ , F ′ ) 上で LP–split2–star を解く． 5: 各 xf = 0 となる辺を全て除く． 6: 各 u ∈ I ′ と v ∈ N (u) に対して，x{u,v} = 1 ならば T ′ := T ′ ∪ {u, v}, I ′ := I ′ \ {u}, B{v,v1 } := B{v,v1 } − (deg(u) − 2) に更新． 7: degF ′ (v) = 0 となる点を全て除く． ∑ 8: 「degF ′ (v) = 2 かつ u∈I x{u,v} ≥ 1」または「degF ′ (v) = 1」 ′ を満たす v ∈ C \ {v1 } が存在するなら I ′ := I ′ \ NF ′ (v), C ′ := C ′ \ {v} とし, T ′ に v から出ている F ′ の辺を全て加える． 9: end while 10: return T ′. 5.3 split グラフ上の全域木混雑度の上界 この節では，前節と同様の手法を用いたアルゴリズム. ゴリズムが正しく動作することを保証するための補題を証. を設計し，split グラフの全域木混雑度の上界を導出する．. 明する．方針はほぼ補題 5.6 と同様である．. deg(v1 ) ≥ deg(v2 ) ≥, ..., ≥ deg(v|V | ) とする．次の定理を. 補題 5.10. x を全ての要素が小数値であるような LP–. 証明する．. split2–star の端点解とする．このとき，次の条件のどちら. 定理 5.8. 任意の split グラフに対して，stc(G) ≤ 2deg(v2 )．. か１つを満たすような頂点 v ∈ C \ {v1 } が存在する．. 本節で設計するアルゴリズムでは最小混雑木の代わりに. v1 を中心とするスターを求め，I の各点を全域木となるよ c 2014 Information Processing Society of Japan ⃝. ( 1 ) degF ′ (v) = 1， ( 2 ) degF ′ (v) = 2 かつ. ∑ u∈I. x{v,u} ≥ 1．. 7.
(8) Vol.2014-AL-150 No.17 2014/11/21. 情報処理学会研究報告 IPSJ SIG Technical Report. 証明.. (1),(2) の両方を満たさないと仮定し，矛盾を導く．. である．. ∑. (i)「任意の v ∈ C \ {v1 } に対して，degF (v) ̸= 1 かつ. degF ′ (v) = 2 かつ. degF (v) ̸= 2」. が存在するとき，v に 2 つの頂点が付け替えられる．こ. degF (v) = 0 となる v ∈ C \ {v1 } はアルゴリズムにより除. の 頂 点 を u1 , u2 と す る ．u1 , u2 が v に 付 け 替 え ら れ る. かれるので，任意ｎ v ∈ C \ {v1 } に対して，degF (v) > 2 と なので，任意の u ∈ I に対して degF (u) ≥ 2 が成り立つ．. 直 前 ま で に v に 付 け 替 え ら れ た 頂 点 の 集 合 を Iv∗ と す ∑ る．アルゴリズムから B{v1 ,v} ≥ u∈Iv∗ (deg(u) − 2) + ∑ i=1,2 (deg(ui ) − 2)x{u1 ,v} である．u1 , u2 の付け替え後. 補題 5.9 から，|F | = |I| + |C ∗ | である．よって. は高々. 仮定する．24 式を満たし，かつ任意の f に対して xf < 1. ∑. |I| + |C ∗ | = |F | ∑ ∑ u∈I degF (u) + v∈C degF (v) = 2 > |I| + |C| − 1. u∈I. x{v,u} ≥ 1 となる頂点 v ∈ C \{v1 }. u∈Iv∗. ≤ B{v,v1 } + (握手補題より). ∑ i=1,2. ≤ B{v,v1 } + (2 −. ((19) 式と背理法の仮定より). ∑. (deg(u) − 2) +. (deg(ui ) − 2). i=1,2. (deg(ui ) − 2)(1 − x{ui ,v} ) ∑. x{ui ,v} )(|C| − 2). i=1,2. ≥ |I| + |C ∗ |. ≤ B{v,v1 } + |C| − 2.. となり，矛盾．. (ii)「任意の v ∈ C \ {v1 } に対して degF (v) ̸= 1 かつ ∑ u∈I x{v,u} < 1」 (i) と同様の理由で任意の v ∈ C\{v1 } に対して degF (v) ≥ 2 と仮定できる．また，任意の u ∈ I ′ に対して，degF ′ (u) ≥ 2 が成り立つ．補題 5.9 より，. 最後の不等式は. ∑ i=1,2. x{ui ,v} ≥ 1 よ り 導 か れ る ．. deg(v) = Be + |C| − 1 なので，補題が成り立つ． 定理 5.8 の証明. T は v1 を 中 心 と す る ス タ ー な の で ，. cngG (T ) = deg(v2 )．補題 5.11 より，アルゴリズムの出力 T ′ と任意の v ∈ C\{v1 } に対して，cngT ′ ({v1 , v}) ≤ 2deg(v) ≤. 2deg(v2 )．よって stc(G) ≤ cngG (T ′ ) ≤ 2deg(v2 )．. ∗. |I| + |C | = |F | ∑ ∑ degF (u) + v∈C degF (v) = u∈I 2 ≥ |I| + |C| − 1. 6. おわりに (握手補題より). ((19) 式と背理法の仮定より). ≥ |I| + |C ∗ |. よって全ての不等式が等号で成り立つ．すなわち任意の w ∈. I ∪C \{v1 } に対して，degF (w) = 2 であり，degF (v1 ) = 0 で ある．|F | = 2|I| かつ |F | = 2|C| なので，|I| = |C| である． ∑ ∑ ∑ (24) 式より， f ∈F xf = u∈I v∈N (u) x{u,v} = |I| であ ∑ る．一方，任意の v ∈ C \ {v1 } に対して， u∈I x{v,u} < 1 ∑ ∑ なので， v∈C u∈I x{v,u} < |C| である．これは |I| = |C| に矛盾する．. Algorithm3 が出力する全域木の混雑度が高々 2deg(v2 ) であることを証明する．. 本稿では split グラフ上の全域木混雑度問題についてのべ た．まず LP 緩和を行い，それに基づく乱択丸め近似アル ゴリズムを設計した．次に反復丸めアルゴリズムを用いた 近似アルゴリズムを設計した．今後の課題は近似アルゴリ ズムの改善と，今回の反復丸めアルゴリズムを別のグラフ に応用できるかどうかを調査することなどが挙げられる． 参考文献 [1]. [2]. [3]. 補題 5.11. T はスターとする．v ∈ C \ {v1 } は任意とす る．このとき，Algorithm3 の出力 T ′ の各 e = {v1 , v} の混. [4]. 雑度は高々 deg(v) + Be + |C| − 2 ≤ 2deg(v)． 証明.. 定理 5.4 のときと同様，アルゴリズムの 6 行目では. [5]. 制約式を違反しないので，混雑度の増加は高々 Be である．. degF ′ (v) = 1 となるような v ∈ C ′ \{v1 } が存在するとき，v に高々１つ I の頂点が付け替えられ，これ以上 e の混雑度が. [6]. K. Kozawa, Y. Otachi, K. Yamazaki On spanning tree congestion of graphs, Discrete Mathematics, 309 (2009), pp. 4215–4224. L. C. Lau, R. Ravi, M. Singh, Iterative methods in combinatorial optimization, Cambridge University Press (2011). C. Lowenstein, D. Rautenbach, F. Regen, On spanning tree congestion, Discrete Mathematics, 310 (2010), pp. 4653–4655. Y. Okamoto, Y. Otachi, R. Uehara, T. Uno, Hardness results and an exact exponential algorithm for the spanning tree congestion problem, Lecture Notes in Computer Science, 6648 (2011), pp. 452–462. M. I. Ostrovskii, Minimal congestion trees, Discrete Mathematics, 285 (2004), pp. 219–226. S. Simonson, A variation on the min cut linear arrangement problem, Mathematical System Theory, 20 (1987), pp. 235–252.. 増加することはない．deg(u) ≤ |C| なので，Algorithm2 に よる e の混雑度の増加は高々 Be +deg(u)−2 ≤ Be +|C|−2. c 2014 Information Processing Society of Japan ⃝. 8.
(9)
関連したドキュメント
複雑性・多様性を有する健康問題の解決を図り、保健師の使命を全うするに は、地域の人々や関係者・関係機関との
Eckstein: Dual coordinate step methods for linear network flow problems, Mathematical Programming 42 (1988)
東京工業大学
This chapter proposes an efficient algorithm for obtaining K best solutions to the simple resource allocation problem. It partitions the solution space into small subsets step by
Approximating minimum bounded degree spanning trees to within one of optimal. Iterative Rounding for Multi-Objective
Vondrák: Optimal approximation for the submodular welfare problem in the value oracle model, STOC 2008,
Murota: Discrete Convex Analysis (SIAM Monographs on Dis- crete Mathematics and Applications 10, SIAM, 2003). Fujishige: Submodular Functions and Optimization (Annals of
Karzanov: Minimum 0-extensions of graph metrics, Europ.. Metric relaxation (Karzanov
