论文标题
在周期中寻找公平独立集的复杂性
The Complexity of Finding Fair Independent Sets in Cycles
论文作者
论文摘要
令$ g $为循环图，让$ v_1，\ ldots，v_m $是其顶点设置为$ m $ sets的分区。如果$ | s \ cap v_i | \ geq \ frac {1} {2} \ cdot | v_i | -1 $ in [m] $中的所有$ i \。众所周知，在每个周期及其顶点集的每个分区中，都存在一个公平代表分区的独立集（Aharoni等人，经过离散数学的旅程，2017年）。我们证明，找到这样的独立集的问题是$ \ mathsf {ppa} $ - 完整。作为一个应用程序，我们表明在Schrijver图中找到单色边缘的问题，鉴于使用颜色少于其色数的颜色的简洁表示，是$ \ Mathsf {ppa} $ - 也可以完成。这项工作是由“循环加三角形”问题及其扩展问题的计算方面激励的。
Let $G$ be a cycle graph and let $V_1,\ldots,V_m$ be a partition of its vertex set into $m$ sets. An independent set $S$ of $G$ is said to fairly represent the partition if $|S \cap V_i| \geq \frac{1}{2} \cdot |V_i| -1$ for all $i \in [m]$. It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al., A Journey through Discrete Math., 2017). We prove that the problem of finding such an independent set is $\mathsf{PPA}$-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is $\mathsf{PPA}$-complete as well. The work is motivated by the computational aspects of the `cycle plus triangles' problem and of its extensions.
