The Complexity of Finding Fair Independent Sets in Cycles

Abstract

Let $G$ be a cycle graph and let $V_1,\dots ,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|\ge \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.

arXiv comment20 pages