Fixed-Parameter Algorithms for the Kneser and Schrijver Problems

. The Kneser graph \ (K (n, k) \) is defined for integers \ (n\) and \ (k\) with \ (n 2k\) as the graph whose vertices are all the \ (k\) -subsets of \ (n=\1, 2, , n\\) where two such sets are adjacent if they are disjoint. The Schrijver graph \ (S (n, k) \) is defined as the subgraph of \ (K (n, k) \) induced by the collection of all \ (k\) -subsets of \ (n\) that do not include two consecutive elements modulo \ (n\). It is known that the chromatic number of both \ (K (n, k) \) and \ (S (n, k) \) is \ (n-2k+2\). In the computational Kneser and Schrijver problems, we are given access to a coloring with \ (n-2k+1\) colors of the vertices of \ (K (n, k) \) and \ (S (n, k) \), respectively, and the goal is to find a monochromatic edge. We prove that the problems admit randomized algorithms with running time \ (n^O (1) k^O (k) \), hence they are fixed-parameter tractable with respect to the parameter \ (k\). The analysis involves structural results on intersecting families and on induced subgraphs of Kneser and Schrijver graphs. We also study the Agreeable-Set 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 polynomial-time algorithm for the Agreeable-Set problem for instances with \ (m - O (m m) \). We further show that the Agreeable-Set problem is at least as hard as a variant of the Kneser problem with extended access to the input coloring. KeywordsKneser graphsSchrijver graphsagreeable setfixed-parameter tractabilityMSC codes05C8505C1568Q27