Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
From MaRDI portal
Publication:6154195
DOI10.1137/23m1557076arXiv2204.09009OpenAlexW4392776354MaRDI QIDQ6154195
Publication date: 19 March 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2204.09009
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kneser's conjecture, chromatic number, and homotopy
- On total functions, existence theorems and computational complexity
- A short proof of Kneser's conjecture
- The relative complexity of NP search problems
- On the complexity of the parity argument and other inefficient proofs of existence
- Diversity of uniform intersecting families
- Topological lower bounds for the chromatic number: a hierarchy
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- A combinatorical proof of Kneser's conjecture
- The complexity of finding fair independent sets in cycles
- Computing a small agreeable set of indivisible items
- Consensus halving for sets of items
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersecting Families are Essentially Contained in Juntas
- INTERSECTING FAMILIES OF SEPARATED SETS
- Kernelization
- The complexity of splitting necklaces and bisecting ham sandwiches
- Consensus halving is PPA-complete
- Parameterized Algorithms
- A Moment Problem in L 1 Approximation
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Consensus-Halving: Does It Ever Get Easier?
