论文标题
Gerrymandering的参数化复杂性
Parameterized Complexity of Gerrymandering
论文作者
论文摘要
在代表民主中，选举过程涉及将地理空间划分为每个选举单个代表的地区。这些代表对立法进行制作和投票，激励政党赢得尽可能多的地区（理想情况下是多数）。 Gerrymandering是操纵地区边界以利用所需候选人或政党的优势的过程。我们研究了由Cohen-Zemach等人正式正式正式化的GerryMandering参数化复杂性，这是一个图形问题（与欧几里得空间相对）。 （AAMAS 2018）和ITO等。 （AAMAS 2019）区域将顶点分为连接的子图。我们证明，与区域$ k $的数量相对于树木的数量（即使深度为两个），单位重量是W [2] -HARD。此外，我们表明单位重量gerrymandering仍然是$ \ ell $叶子的树木中的hard [2] - 相对于组合参数$ k+\ ell $。相反，Gupta等人。 （SAGT 2021）给出了关于$ k $的路径的FPT算法。为了补充我们的结果并填补这一空白，我们提供了一种算法来解决当$ \ ell $是一个固定常数时，该算法以$ k $为fpt。
In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft and vote on legislation, incentivizing political parties to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which district boundaries are manipulated to the advantage of a desired candidate or party. We study the parameterized complexity of Gerrymandering, a graph problem (as opposed to Euclidean space) formalized by Cohen-Zemach et al. (AAMAS 2018) and Ito et al. (AAMAS 2019) where districts partition vertices into connected subgraphs. We prove that Unit Weight Gerrymandering is W[2]-hard on trees (even when the depth is two) with respect to the number of districts $k$. Moreover, we show that Unit Weight Gerrymandering remains W[2]-hard in trees with $\ell$ leaves with respect to the combined parameter $k+\ell$. In contrast, Gupta et al. (SAGT 2021) give an FPT algorithm for Gerrymandering on paths with respect to $k$. To complement our results and fill this gap, we provide an algorithm to solve Gerrymandering that is FPT in $k$ when $\ell$ is a fixed constant.
