2026-07-24T03:16:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16413 2024-03-06T10:57:25Z ddc:004 open_access

A Fixed-Parameter Algorithm for the Kneser Problem Haviv, Ishay Kneser graph Fixed-parameter tractability Agreeable Set 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}/{log log 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.72 urn:nbn:de:0030-drops-164139 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.72 eng https://creativecommons.org/licenses/by/4.0/legalcode