The complexity of finding fair independent sets in cycles

DOI10.1007/s00037-022-00233-6OpenAlexW3096701049MaRDI QIDQ2087771

Ishay Haviv

Publication date: 21 October 2022

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.01770

zbMATH Keywords

Schrijver graphsfair independent sets in cyclesthe complexity class \textsf{PPA}

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On finding constrained independent sets in cycles ⋮ Fixed-Parameter Algorithms for the Kneser and Schrijver Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The chromatic number of almost stable Kneser hypergraphs
• Kneser's conjecture, chromatic number, and homotopy
• On total functions, existence theorems and computational complexity
• On the complexity of 2D discrete fixed point problem
• How easy is local search?
• Colorings and orientations of graphs
• A solution to a colouring problem of P. Erdős
• The Hamiltonian property of consecutive-\(d\) digraphs
• On the complexity of the parity argument and other inefficient proofs of existence
• Generalized Kneser coloring theorems with combinatorial proofs
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• A combinatorical proof of Kneser's conjecture
• 2-D Tucker is PPA complete
• Fair splittings by independent sets in sparse graphs
• Unique end of potential line
• The Hairy Ball problem is PPAD-complete
• Computing a small agreeable set of indivisible items
• An algorithm for identifying cycle-plus-triangles graphs
• Fair splitting of colored paths
• Consensus halving for sets of items
• Bisection of Circle Colorings
• Settling the complexity of computing two-player Nash equilibria
• Combinatorial Nullstellensatz
• Fair Representation by Independent Sets
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Algorithmic Solutions for Envy-Free Cake Cutting
• The Complexity of Computing a Nash Equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• Consensus halving is PPA-complete
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg