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 \(nO(1) · kO(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(log m/log log 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.