论文标题
关于在几乎单峰偏好下建设性控制的复杂性
On the Complexity of Constructive Control under Nearly Single-Peaked Preferences
论文作者
论文摘要
我们通过添加/删除投票}}}}}}（ccav/ccdv）的复杂性，以$ r $ - 批准，condorcet，maxorcet，maxorcimin和copeland $ k $ - $ k $ axe和$ k $ - $ k $ - candidates $ k $ - candidates apatientates单口销售的选举。通常，我们证明，即使〜$ k $是一个很小的常数，上面提到的大多数投票信件的CCAV和CCDV也是NP-HARD。 CCAV和CCDV的例外是Condorcet和CCAV，$ r $ $ $ $ $ k $ axes的单峰选举的例外，我们表明与〜$ k $相对于固定参数可进行固定参数。此外，我们还提供了多项式时间算法，以识别$ 2 $轴的选举，从而解决了一个空旷的问题。我们的工作导致许多二分法结果。为了建立NP硬度结果，我们还研究了可能具有独立关注的$ 3 $定型两分图的财产。特别是，我们证明，对于每两$ 3 $的双分图图，其顶点的两个线性顺序，因此每个边缘的两个端点至少在两个订单中的至少一个是连续的。
We investigate the complexity of {\sc{Constructive Control by Adding/Deleting Votes}} (CCAV/CCDV) for $r$-approval, Condorcet, Maximin and Copeland$^α$ in $k$-axes and $k$-candidates partition single-peaked elections. In general, we prove that CCAV and CCDV for most of the voting correspondences mentioned above are NP-hard even when~$k$ is a very small constant. Exceptions are CCAV and CCDV for Condorcet and CCAV for $r$-approval in $k$-axes single-peaked elections, which we show to be fixed-parameter tractable with respect to~$k$. In addition, we give a polynomial-time algorithm for recognizing $2$-axes elections, resolving an open problem. Our work leads to a number of dichotomy results. To establish an NP-hardness result, we also study a property of $3$-regular bipartite graphs which may be of independent interest. In particular, we prove that for every $3$-regular bipartite graph, there are two linear orders of its vertices such that the two endpoints of every edge are consecutive in at least one of the two orders.
