The complexity of finding fair independent sets in cycles
type: Item
instance of: scholarly article
title: The complexity of finding fair independent sets in cycles
author: Ishay Haviv
published in: Computational Complexity
publication date: 2022-10-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/2011.01770
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7605017
zbMATH Keywords: fair independent sets in cycles
zbMATH Keywords: the complexity class \textsf{PPA}
zbMATH Keywords: Schrijver graphs
MaRDI profile type: Publication
OpenAlex ID: W3096701049
cites work: Fair Representation by Independent Sets
cites work: 2-D Tucker is PPA complete
cites work: Fair splitting of colored paths
cites work: Combinatorial Nullstellensatz
cites work: Q4418777
cites work: Colorings and orientations of graphs
cites work: The Borsuk-Ulam Theorem and Bisection of Necklaces
cites work: Q5111161
cites work: An algorithm for identifying cycle-plus-triangles graphs
cites work: Fair splittings by independent sets in sparse graphs
cites work: On the complexity of 2D discrete fixed point problem
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Q5365081
cites work: The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
cites work: Algorithmic Solutions for Envy-Free Cake Cutting
cites work: The Hamiltonian property of consecutive-\(d\) digraphs
cites work: Q3983100
cites work: Unique end of potential line
cites work: Consensus halving is PPA-complete
cites work: The complexity of splitting necklaces and bisecting ham sandwiches
cites work: A solution to a colouring problem of P. Erdős
cites work: Q5689006
cites work: Bisection of Circle Colorings
cites work: The Hairy Ball problem is PPAD-complete
cites work: Consensus halving for sets of items
cites work: How easy is local search?
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: Computing a small agreeable set of indivisible items
cites work: A combinatorical proof of Kneser's conjecture
cites work: On total functions, existence theorems and computational complexity
cites work: The chromatic number of almost stable Kneser hypergraphs
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Consensus-halving via theorems of Borsuk-Ulam and Tucker
cites work: Generalized Kneser coloring theorems with combinatorial proofs
DOI: 10.1007/S00037-022-00233-6
description: scientific article; zbMATH DE number 7605017