论文标题
操纵地区赢得选举：细粒度的复杂性
Manipulating Districts to Win Elections: Fine-Grained Complexity
论文作者
论文摘要
Gerrymandering是一种操纵地区边界和地点的做法，以便为特定政党获得政治优势。 Lewenberg，Lev和Rosenschein [Aamas 2017]启动了对基于地理的操纵问题的算法研究，选民必须在最接近他们的投票箱上投票。在这一变体中，对于给定的一组可能的投票箱和已知的$ n $选民的政治偏好的位置，其任务是确定$ k $ boxes的位置，以确保至少在$ l $ $地区的某个政党的胜利。这里的整数$ k $和$ l $是一些选定的参数。 众所周知，这个问题已经在4个政党中已经是NP完整的，并且在我们的工作之前，只有针对此问题的启发式算法才得以开发。我们从参数化和细粒度的复杂性的角度开始对Gerrymandering问题进行严格研究，并在其计算复杂性上提供渐近匹配的下限和上限。 We prove that the problem is W[1]-hard parameterized by $k+n$ and that it does not admit an $f(n,k)\cdot m^{o(\sqrt{k})}$ algorithm for any function $f$ of $k$ and $n$ only, unless Exponential Time Hypothesis (ETH) fails.我们的下限已经以2美元的派对为生。另一方面，我们给出了一种算法，该算法解决了时间$（m+n）^{o（\ sqrt {k}）} $的恒定派对数量的问题。
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of $n$ voters, the task is to identify locations for $k$ boxes out of $m$ possible locations to guarantee victory of a certain party in at least $l$ districts. Here integers $k$ and $l$ are some selected parameter. It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by $k+n$ and that it does not admit an $f(n,k)\cdot m^{o(\sqrt{k})}$ algorithm for any function $f$ of $k$ and $n$ only, unless Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for $2$ parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time $(m+n)^{O(\sqrt{k})}$.
