TY - JOUR

T1 - Algorithms for gerrymandering over graphs

AU - Ito, Takehiro

AU - Kamiyama, Naoyuki

AU - Kobayashi, Yusuke

AU - Okamoto, Yoshio

N1 - 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.

KW - Computational social choice

KW - Gerrymandering

KW - Graph algorithms

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 -