Algorithms for Gerrymandering over Graphs

Transcript

1. グラフ上のGerrymanderingのための アルゴリズム Algorithms for Gerrymandering over Graphs Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Ph.D. 名無しの権兵衛 1
2. ストーリー 2 候補者pを支持する有権者 候補者qを支持する有権者 青×9, 赤×3 とある選挙にて・・・ １.　有権者を区分けする ２.　それぞれの選挙区から候補者を一人を選びだす ３.　勝利した選挙区が最も多い候補者が最終的に当選する 候補者qが当選 青×3, 赤×0 → 青 青×2, 赤×1 → 青 青×4, 赤×2 → 青 青×3, 赤×0 → 青
3. ストーリー 3 候補者pを支持する有権者 候補者qを支持する有権者 青×9, 赤×3 とある選挙にて・・・ 候補者qが当選 どうしても候補者pを勝たせたい！ あなた
4. ストーリー 4 候補者pを支持する有権者 候補者qを支持する有権者 青×9, 赤×3 選挙にて・・・ 候補者pが当選 区分けをうまく割り当てれば候補者pを当選させられるのでは？ あなた 恣意的に区分けを行う：ゲリマンダリング 青×9, 赤×0 → 青 青×0, 赤×2 → 赤 青×0, 赤×1 → 赤 青×1, 赤×2 → 赤
5. ストーリー 5 候補者pを支持する有権者 候補者qを支持する有権者 青×9, 赤×3 選挙にて・・・ 候補者pが当選 区分けをうまく割り当てれば候補者pを当選させられるのでは？ あなた 恣意的に区分けを行う：ゲリマンダリング 青×9, 赤×0 → 青 青×0, 赤×2 → 赤 青×0, 赤×1 → 赤 青×1, 赤×2 → 赤 目的 :ゲリマンダリングが可能か判定するアルゴリズムを 　　 多項式時間で解けるかという観点から調べる
6. ゲリマンダリング 6 1 2 5 3 6 1 Gerrymandering問題 ・入力 ・無向グラフ ・重み(有権者の数) ・候補者の集合 ・目的の候補者 ・分割数 ・出力 ・目的の候補者が単独で勝利する 　連結成分に分割できればYES， 　なければNO q q q q p p 例. 候補者 = {p, q}, 目的候補者p, 分割数=3
7. ゲリマンダリング 7 1 2 5 3 6 1 Gerrymandering問題 ・入力 ・無向グラフ ・重み(有権者の数) ・候補者の集合 ・目的の候補者 ・分割数 ・出力 ・目的の候補者が単独で勝利する 　連結成分に分割できればYES， 　なければNO q q q q p p q=0, p=1 → {p} q = 1+2+3 = 6, p=0 → {q} q=5, p=6 → {p} 出力：q×1, p×2 => YES 例. 候補者 = {p, q}, 目的候補者p, 分割数=3
8. ゲリマンダリング 8 1 2 5 3 6 1 Gerrymandering問題 ・入力 ・無向グラフ ・重み(有権者の数) ・候補者の集合 ・目的の候補者 ・分割数 ・出力 ・目的の候補者が単独で勝利する 　連結成分に分割できればYES， 　なければNO q q q q p p 例. 候補者 = {p, q}, 目的候補者p, 分割数=4
9. ゲリマンダリング 9 1 2 5 3 6 1 Gerrymandering問題 ・入力 ・無向グラフ ・重み(有権者の数) ・候補者の集合 ・目的の候補者 ・分割数 ・出力 ・目的の候補者が単独で勝利する 　連結成分に分割できればYES， 　なければNO q q q q p p 例. 候補者 = {p, q}, 目的候補者p, 分割数=4
10. ゲリマンダリング 10 1 2 5 3 6 1 Gerrymandering問題 ・入力 ・無向グラフ ・重み(有権者の数) ・候補者の集合 ・目的の候補者 ・分割数 ・出力 ・目的の候補者が単独で勝利する 　連結成分に分割できればYES， 　なければNO q q q q p p q = 1+ 5 = 6, p=6 →{p, q} q=2, p=0 → {q} q=3, p=0 → {q} q=0, p=1 → {p} 例. 候補者 = {p, q}, 目的候補者p, 分割数=4 出力：q×3, p×1 => NO タイブレイクを考慮すると目的候補は単独，それ 以外の候補は含むことでカウントする
11. 本論文の結果 11 候補者数|C| : 一般 候補者数|C| : 定数 　　平面　　　　　　 　　木　　　　　　 　スター　　　　　　 　 パス　　　　　　 強NP完全(定理3) 直径4 強NP完全 NP完全(定理1) 分割数k=2, |C| = 4 多項式時間(定理5) 多項式時間 擬多項式時間(定理7) 多項式時間(定理6) ？
12. 本論文の結果 12 候補者数|C| : 一般 候補者数|C| : 定数 　　平面　　　　　　 　　木　　　　　　 　スター　　　　　　 　 パス　　　　　　 強NP完全(定理3) 直径4 強NP完全 NP完全(定理1) 分割数k=2, |C| = 4 多項式時間(定理5) 多項式時間 擬多項式時間(定理7) 多項式時間(定理6) ？ ココ
13. NP完全性 13 定理1 Gerrymandering問題は分割数k=2，候補者数|C|=2， Gが完全二部グラフもしくは完全グラフのときNP完全である e.g. 完全二部グラフ 完全グラフ
14. NP完全性 14 定理1 Gerrymandering問題は分割数k=2，候補者数|C|=2， Gが完全二部グラフもしくは完全グラフのときNP完全である NP完全である Partition問題 Gerrymandering問題 証明. 既にNP完全性が知られているPartition問題から， Gerrymandering問題に多項式時間帰着する
15. Partition問題 15 Partition問題 入力：n個の自然数の集合 a1 ,a2 , … , an 出力： 　　　 　となるようなS∈{1,2,...,n}があればYES，なければNO (例1) 入力 : n = 4,　a1 =1, a2 =3, a3 =1, a4 =1 出力: YES (例2) 入力 : n = 4,　a1 =1, a2 =3, a3 =5, a4 =11 出力: NO S = {1, 3, 4}のとき a1 + a3 + a4 =1 + 1 + 1 = 3 a2 = 3 条件を満たす Sは存在しない
16. インスタンスの変換 16 Partition問題 入力 : n = 4,　a1 =1, a2 =3, a3 =1, a4 =1 出力: YES Gerrymandering問題 入力 : 無向グラフ，分割数k=2，候補者数|C|=2 出力 : ？ p p 1 q 3 q 1 q 1 q 3.3 3.3 pを選ぶ重み0.5(a1 +a2 +...+an )+εの頂点を2個 => 0.5(1+3+1+1)+0.3 qを選ぶ a1 , a2 , ..., an に対応した頂点を用意
17. 定理1の証明のポイント 17 p p 1 q 3 q 1 q 1 q 2つの区間に分割を行うときの分割方法 3.3 3.3 Partition問題のインスタンス a1 =1, a2 =3, a3 =1, a4 =1 を変換
18. 定理1の証明のポイント 18 p p 1 q 3 q 1 q 1 q 2つの区間に分割を行うときの分割方法 必ず目的候補pを勝たせなければいけない 3.3 3.3 Partition問題のインスタンス a1 =1, a2 =3, a3 =1, a4 =1 を変換 pが勝つべき区間 　 0個 => ✖ pが0個, qが2個となり 実行可能解はない
19. 定理1の証明のポイント 19 p p 1 q 3 q 1 q 1 q 2つの区間に分割を行うときの分割方法 必ず目的候補pを勝たせなければいけない 3.3 3.3 Partition問題のインスタンス a1 =1, a2 =3, a3 =1, a4 =1 を変換 pが勝つべき区間 　 0個 => ✖ 　1個 => ✖ 　 pが1個, qが1個となり 実行可能解はない
20. 定理1の証明のポイント 20 p p 1 q 3 q 1 q 1 q 2つの区間に分割を行うときの分割方法 必ず目的候補pを勝たせなければいけない 3.3 3.3 Partition問題のインスタンス a1 =1, a2 =3, a3 =1, a4 =1 を変換 pが勝つべき区間 　0個 => ✖ 　 1個 => ✖ 　 2個 => ◦ pが2個, qが0個となり 実行可能解があり
21. 定理1の証明のポイント 21 p p 1 q 3 q 1 q 1 q 2つの区間に分割を行うときの分割方法 必ず目的候補pを勝たせなければいけない 目的候補pを選ぶ点は二つしかないので， 各区間に1つずつ分ける すると，2つの区間がおのずと導ける 3.3 3.3 Partition問題のインスタンス a1 =1, a2 =3, a3 =1, a4 =1 を変換 pが勝つべき区間 　0個 => ✖ 　1個 => ✖ 　 2個 => ◦
22. NP完全性 22 定理1 Gerrymandering問題は分割数k=2，候補者数|C|=2， Gが完全二部グラフもしくは完全グラフのときNP完全である NP完全である Partition問題 Gerrymandering問題 証明. 既にNP完全性が知られているPartition問題から， Gerrymandering問題に多項式時間帰着する
23. 本論文の結果 23 候補者数|C| : 一般 候補者数|C| : 定数 　　平面 　　木　　　　　　 　スター　　　　　　 　 パス　　　　　　 強NP完全(定理3) 直径4 強NP完全 NP完全(定理1) 分割数k=2, |C| = 4 多項式時間(定理5) 多項式時間 擬多項式時間(定理7) 多項式時間(定理6) ？ ココ
24. まとめ ・ゲリマンダリング 問題の定義 ・グラフ上でのGerrymandering問題の困難性の証明 ・Gerrymandering問題の多項式時間アルゴリズム構築 24