The complexity of finding fair independent sets in cycles

DOI10.1007/S00037-022-00233-6MaRDI QIDQ2087771zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Fair representation by independent sets
• Fair Packing of Independent Sets
• Fair splittings by independent sets in sparse graphs
• An algorithm for identifying cycle-plus-triangles graphs
• The complexity for partitioning graphs by monochromatic trees, cycles and paths

Cites work

• scientific article; zbMATH DE number 25254 (Why is no real title available?)
• scientific article; zbMATH DE number 1962903 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• scientific article; zbMATH DE number 970801 (Why is no real title available?)
• 2-D Tucker is PPA complete
• A combinatorical proof of Kneser's conjecture
• A solution to a colouring problem of P. Erdős
• Algorithmic solutions for envy-free cake cutting
• An algorithm for identifying cycle-plus-triangles graphs
• Bisection of Circle Colorings
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Computing a small agreeable set of indivisible items
• Consensus halving for sets of items
• Consensus halving is PPA-complete
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Fair representation by independent sets
• Fair splitting of colored paths
• Fair splittings by independent sets in sparse graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• How easy is local search?
• Kneser's conjecture, chromatic number, and homotopy
• On the complexity of 2D discrete fixed point problem
• On the complexity of the parity argument and other inefficient proofs of existence
• On the polynomial parity argument complexity of the combinatorial Nullstellensatz
• On total functions, existence theorems and computational complexity
• Settling the complexity of computing two-player Nash equilibria
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The Hairy Ball problem is PPAD-complete
• The Hamiltonian property of consecutive-\(d\) digraphs
• The chromatic number of almost stable Kneser hypergraphs
• The complexity of computing a Nash equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Unique end of potential line

Cited in

(3)

• On finding constrained independent sets in cycles
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• Fair splittings by independent sets in sparse graphs

This page was built for publication: The complexity of finding fair independent sets in cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2087771)