Algorithms for Gerrymandering over Graphs
Algorithms for Gerrymandering over Graphs
复制标题
DOI：
10.1016/j.tcs.2021.03.037
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;Naoyuki Kamiyama;Yusuke Kobayashi;Y. Okamoto
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naoyuki Kamiyama;Yusuke Kobayashi;Y. Okamoto
我们发起了系统的算法研究gerrymandering的图，最近推出的Cohen-Zemach，Lewenberg和Rosenschein。也就是说，我们研究了一个策略性的程序，政治分区设计师绘制选区边界，使特定的目标候选人可以在选举中获胜。我们专注于存在这样一个策略下的多数表决规则，并给出有趣的对比，容易和困难的情况下，多项式时间的可解性进行分类。例如，我们证明了树的问题是强NP完全的（因此不太可能有伪多项式时间算法），但当候选人的数量是常数时，有一个伪多项式时间算法。另一个例子是证明了当选举区数为2时，完全图问题是NP-完全的，而当选举区数大于2时，完全图问题是多项式时间可解的。
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 stronglyNP-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 isNP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.