Abstract
The Kneser graph K(n,k) is defined for integers n and k with n ≥ 2k as the graph whose vertices are all the ksubsets of {1,2,…,n} where two such sets are adjacent if they are disjoint. A classical result of Lovász asserts that the chromatic number of K(n,k) is n2k+2. In the computational Kneser problem, we are given an oracle access to a coloring of the vertices of K(n,k) with n2k+1 colors, and the goal is to find a monochromatic edge. We present a randomized algorithm for the Kneser problem with running time n^O(1) ⋅ k^O(k). This shows that the problem is fixedparameter tractable with respect to the parameter k. The analysis involves structural results on intersecting families and on induced subgraphs of Kneser graphs.
We also study the AgreeableSet problem of assigning a small subset of a set of m items to a group of 𝓁 agents, so that all agents value the subset at least as much as its complement. As an application of our algorithm for the Kneser problem, we obtain a randomized polynomialtime algorithm for the AgreeableSet problem for instances that satisfy 𝓁 ≥ m  O({log m}/{log log m}). We further show that the AgreeableSet problem is at least as hard as a variant of the Kneser problem with an extended access to the input coloring.
BibTeX  Entry
@InProceedings{haviv:LIPIcs.ICALP.2022.72,
author = {Haviv, Ishay},
title = {{A FixedParameter Algorithm for the Kneser Problem}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {72:172:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16413},
URN = {urn:nbn:de:0030drops164139},
doi = {10.4230/LIPIcs.ICALP.2022.72},
annote = {Keywords: Kneser graph, Fixedparameter tractability, Agreeable Set}
}
Keywords: 

Kneser graph, Fixedparameter tractability, Agreeable Set 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 