TY - JOUR
T1 - Algorithms for gerrymandering over graphs
AU - Ito, Takehiro
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Okamoto, Yoshio
N1 - Funding Information:
The first author was partially supported by JST CREST Grant Number JPMJCR1402 , and JSPS KAKENHI Grant Numbers JP16K00004 , JP18H04091 , JP19K11814 , and JP20H05793 . The second author was partially supported by JST , PRESTO Grant Number JPMJPR1753 , Japan. The third author was partially supported by JST ACT-I Grant Number JPMJPR17UB , and JSPS KAKENHI Grant Numbers JP16K16010 , JP18H05291 , JP19H05485 , JP20K11692 , and JP20H05795 . The fourth author was partially supported by JSPS KAKENHI Grant Numbers JP15K00009 , JP20K11670 , JP20H05795 , JST CREST Grant Number JPMJCR1402 , and Kayamori Foundation of Informational Science Advancement .
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/5/8
Y1 - 2021/5/8
N2 - We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.
AB - We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.
UR - http://www.scopus.com/inward/record.url?scp=85103519376&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103519376&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2021.03.037
DO - 10.1016/j.tcs.2021.03.037
M3 - Article
AN - SCOPUS:85103519376
SN - 0304-3975
VL - 868
SP - 30
EP - 45
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -