License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.72
URN: urn:nbn:de:0030-drops-164139
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16413/
Go to the corresponding LIPIcs Volume Portal

Haviv, Ishay

A Fixed-Parameter Algorithm for the Kneser Problem

pdf-format:
LIPIcs-ICALP-2022-72.pdf (0.7 MB)

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 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.

BibTeX - Entry

@InProceedings{haviv:LIPIcs.ICALP.2022.72,
  author =	{Haviv, Ishay},
  title =	{{A Fixed-Parameter Algorithm for the Kneser Problem}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{72:1--72:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16413},
  URN =		{urn:nbn:de:0030-drops-164139},
  doi =		{10.4230/LIPIcs.ICALP.2022.72},
  annote =	{Keywords: Kneser graph, Fixed-parameter tractability, Agreeable Set}
}

Keywords: Kneser graph, Fixed-parameter tractability, Agreeable Set
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI