グラフ上のGerrymanderingのためのアルゴリズム
Algorithms for Gerrymandering over Graphs
Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Ph.D.
名無しの権兵衛
1
ストーリー
2
候補者pを支持する有権者
候補者qを支持する有権者
青×9, 赤×3
とある選挙にて・・・
１. 有権者を区分けする
２. それぞれの選挙区から候補者を一人を選びだす
３. 勝利した選挙区が最も多い候補者が最終的に当選する
候補者qが当選
青×3, 赤×0
→ 青
青×2, 赤×1
→ 青
青×4, 赤×2
→ 青
青×3, 赤×0
→ 青
ストーリー
3
候補者pを支持する有権者
候補者qを支持する有権者
青×9, 赤×3
とある選挙にて・・・
候補者qが当選
どうしても候補者pを勝たせたい！
あなた
ストーリー
4
候補者pを支持する有権者
候補者qを支持する有権者
青×9, 赤×3
選挙にて・・・
候補者pが当選
区分けをうまく割り当てれば候補者pを当選させられるのでは？
あなた
恣意的に区分けを行う：ゲリマンダリング
青×9, 赤×0
→ 青
青×0, 赤×2
→ 赤
青×0, 赤×1
→ 赤
青×1, 赤×2
→ 赤
ストーリー
5
候補者pを支持する有権者
候補者qを支持する有権者
青×9, 赤×3
選挙にて・・・
候補者pが当選
区分けをうまく割り当てれば候補者pを当選させられるのでは？
あなた
恣意的に区分けを行う：ゲリマンダリング
青×9, 赤×0
→ 青
青×0, 赤×2
→ 赤
青×0, 赤×1
→ 赤
青×1, 赤×2
→ 赤
目的 :ゲリマンダリングが可能か判定するアルゴリズムを
多項式時間で解けるかという観点から調べる
ゲリマンダリング
6
1
2
5
3
6
1
Gerrymandering問題
・入力
・無向グラフ
・重み(有権者の数)
・候補者の集合
・目的の候補者
・分割数
・出力
・目的の候補者が単独で勝利する
連結成分に分割できればYES，
なければNO
q
q
q
q
p
p
例. 候補者 = {p, q}, 目的候補者p, 分割数=3
ゲリマンダリング
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
1
2
5
3
6
1
Gerrymandering問題
・入力
・無向グラフ
・重み(有権者の数)
・候補者の集合
・目的の候補者
・分割数
・出力
・目的の候補者が単独で勝利する
連結成分に分割できればYES，
なければNO
q
q
q
q
p
p
例. 候補者 = {p, q}, 目的候補者p, 分割数=4
ゲリマンダリング
9
1
2
5
3
6
1
Gerrymandering問題
・入力
・無向グラフ
・重み(有権者の数)
・候補者の集合
・目的の候補者
・分割数
・出力
・目的の候補者が単独で勝利する
連結成分に分割できればYES，
なければNO
q
q
q
q
p
p
例. 候補者 = {p, q}, 目的候補者p, 分割数=4
ゲリマンダリング
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
| 候補者数|C| : 一般 | 候補者数|C| : 定数 |
平面 | | |
木 | | |
スター | | |
パス | | |
強NP完全(定理3)
直径4
強NP完全
NP完全(定理1)
分割数k=2, |C| = 4
多項式時間(定理5)
多項式時間
擬多項式時間(定理7)
多項式時間(定理6)
？
本論文の結果
12
| 候補者数|C| : 一般 | 候補者数|C| : 定数 |
平面 | | |
木 | | |
スター | | |
パス | | |
強NP完全(定理3)
直径4
強NP完全
NP完全(定理1)
分割数k=2, |C| = 4
多項式時間(定理5)
多項式時間
擬多項式時間(定理7)
多項式時間(定理6)
？
ココ
NP完全性
13
定理1
Gerrymandering問題は分割数k=2，候補者数|C|=2，
Gが完全二部グラフもしくは完全グラフのときNP完全である
e.g.
完全二部グラフ
完全グラフ
NP完全性
14
定理1
Gerrymandering問題は分割数k=2，候補者数|C|=2，
Gが完全二部グラフもしくは完全グラフのときNP完全である
NP完全である
Partition問題
Gerrymandering問題
証明.
既にNP完全性が知られているPartition問題から，
Gerrymandering問題に多項式時間帰着する
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
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に対応した頂点を用意
定理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 を変換
定理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個となり
実行可能解はない
定理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個となり
実行可能解はない
定理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個となり
実行可能解があり
定理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個 => ○
NP完全性
22
定理1
Gerrymandering問題は分割数k=2，候補者数|C|=2，
Gが完全二部グラフもしくは完全グラフのときNP完全である
NP完全である
Partition問題
Gerrymandering問題
証明.
既にNP完全性が知られているPartition問題から，
Gerrymandering問題に多項式時間帰着する
本論文の結果
23
| 候補者数|C| : 一般 | 候補者数|C| : 定数 |
平面 | | |
木 | | |
スター | | |
パス | | |
強NP完全(定理3)
直径4
強NP完全
NP完全(定理1)
分割数k=2, |C| = 4
多項式時間(定理5)
多項式時間
擬多項式時間(定理7)
多項式時間(定理6)
？
ココ
まとめ
24
・ゲリマンダリング 問題の定義
・グラフ上でのGerrymandering問題の困難性の証明
・Gerrymandering問題の多項式時間アルゴリズム構築