Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Algorithms for Gerrymandering over Graphs
Search
hanachiru
July 27, 2020
Education
0
210
Algorithms for Gerrymandering over Graphs
hanachiru
July 27, 2020
Tweet
Share
More Decks by hanachiru
See All by hanachiru
1時間でフラグメントシェーダー入門からボロノイ図まで
hanachiru
0
1.7k
Other Decks in Education
See All in Education
Master of Applied Science & Engineering: Computer Science & Master of Science in Applied Informatics: Artificial Intelligence and Data Science
signer
PRO
0
830
Introdución ás redes
irocho
0
220
20250830_本社にみんなの公園を作ってみた
yoneyan
0
130
アントレプレナーシップ教育 ~ 自分で自分の幸せを決めるために ~
yoshizaki
0
210
GOVERNOR ADDRESS:2025年9月29日合同公式訪問例会:2720 Japan O.K. ロータリーEクラブ、2025年10月6日卓話:藤田 千克由 氏(国際ロータリー第2720地区 2025-2026年度 ガバナー・大分中央ロータリークラブ・大分トキハタクシー(株)顧問)
2720japanoke
0
560
20250625_なんでもCopilot 一年の振り返り
ponponmikankan
0
380
沖ハック~のみぞうさんとハッキングチャレンジ☆~
nomizone
1
240
今の私を形作る4つの要素と偶然の出会い(セレンディピティ)
mamohacy
2
110
[Segah 2025] Gamified Interventions for Composting Behavior in the Workplace
ezefranca
0
160
American Airlines® USA Contact Numbers: The Ultimate 2025 Guide
lievliev
0
260
Alumnote inc. Company Deck
yukinumata
0
3.2k
Adobe Express
matleenalaakso
1
8k
Featured
See All Featured
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.7k
Statistics for Hackers
jakevdp
799
220k
Mobile First: as difficult as doing things right
swwweet
224
10k
A Tale of Four Properties
chriscoyier
160
23k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Gamification - CAS2011
davidbonilla
81
5.5k
Optimising Largest Contentful Paint
csswizardry
37
3.4k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Intergalactic Javascript Robots from Outer Space
tanoku
273
27k
The Straight Up "How To Draw Better" Workshop
denniskardys
237
140k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
140
34k
A better future with KSS
kneath
239
18k
Transcript
グラフ上のGerrymanderingのための アルゴリズム Algorithms for Gerrymandering over Graphs Takehiro Ito, Naoyuki
Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Ph.D. 名無しの権兵衛 1
ストーリー 2 候補者pを支持する有権者 候補者qを支持する有権者 青×9, 赤×3 とある選挙にて・・・ 1. 有権者を区分けする 2. それぞれの選挙区から候補者を一人を選びだす 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) ? ココ
まとめ ・ゲリマンダリング 問題の定義 ・グラフ上でのGerrymandering問題の困難性の証明 ・Gerrymandering問題の多項式時間アルゴリズム構築 24