The Complexity of Finding Fair Independent Sets in Cycles
summary
Shows that finding an independent set in a cycle that picks about half from each given part is PPA-complete, and that the version asking for two disjoint such sets covering all but one vertex per part is also PPA-complete while an approximate variant becomes PPAD-hard. Reduction starts from Consensus Halving: piecewise-constant measures get discretized into vertex sets along a path, dummy white vertices are inserted between consecutive original vertices, the path is closed into a cycle, and uncovered vertices by the two independent sets correspond to the cuts that solve the original halving instance.
AI-written summary · about