2026-08-06T02:08:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13543 2024-03-06T10:52:16Z ddc:004 open_access

The Complexity of Finding Fair Independent Sets in Cycles Haviv, Ishay Fair independent sets in cycles the complexity class {PPA} Schrijver graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.4 urn:nbn:de:0030-drops-135431 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.4 eng https://creativecommons.org/licenses/by/3.0/legalcode