Let G be a cycle graph and let V₁,…,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 ∩ V_i| ≥ 1/2⋅|V_i| - 1 for all i ∈ [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 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 PPA-complete as well. The work is motivated by the computational aspects of the "cycle plus triangles" problem and of its extensions.
@InProceedings{haviv:LIPIcs.ITCS.2021.4, author = {Haviv, Ishay}, title = {{The Complexity of Finding Fair Independent Sets in Cycles}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.4}, URN = {urn:nbn:de:0030-drops-135431}, doi = {10.4230/LIPIcs.ITCS.2021.4}, annote = {Keywords: Fair independent sets in cycles, the complexity class \{PPA\}, Schrijver graphs} }
Feedback for Dagstuhl Publishing