  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.

Computational Complexity