A Fixed-Parameter Algorithm for the Kneser Problem
share
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 {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 n-2k+2. In the computational Kneser problem, we are given an oracle access to a coloring of the vertices of K(n,k) with n-2k+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 fixed-parameter 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 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 that satisfy ℓ≥ m - O(log m/loglog m). We further show that the Agreeable-Set problem is at least as hard as a variant of the Kneser problem with an extended access to the input coloring.
READ FULL TEXT