The complexity of finding fair independent sets in cycles

DOI10.1007/S00037-022-00233-6OpenAlexW3096701049MaRDI QIDQ2087771FDOQ2087771

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

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

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)

Cites Work

• The complexity of computing a Nash equilibrium
• Kneser's conjecture, chromatic number, and homotopy
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Combinatorial Nullstellensatz
• Settling the complexity of computing two-player Nash equilibria
• On total functions, existence theorems and computational complexity
• Colorings and orientations of graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• A combinatorical proof of Kneser's conjecture
• The chromatic number of almost stable Kneser hypergraphs
• Title not available (Why is that?)
• A solution to a colouring problem of P. Erdős
• Title not available (Why is that?)
• On the polynomial parity argument complexity of the combinatorial Nullstellensatz
• Bisection of Circle Colorings
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Title not available (Why is that?)
• Algorithmic solutions for envy-free cake cutting
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• On the complexity of 2D discrete fixed point problem
• The Hamiltonian property of consecutive-\(d\) digraphs
• Title not available (Why is that?)
• Fair representation by independent sets
• Consensus halving is PPA-complete
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• 2-D Tucker is PPA complete
• Unique end of potential line
• The complexity of splitting necklaces and bisecting ham sandwiches
• Fair splittings by independent sets in sparse graphs
• 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

Cited In (3)

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

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)