Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911775811698688 |
|---|---|
| author | Haviv, Ishay |
| author_facet | Haviv, Ishay |
| contents | The Kneser graph $K(n,k)$ is defined for integers $n$ and $k$ with $n \geq 2k$ as the graph whose vertices are all the $k$-subsets of $[n]=\{1,2,\ldots,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 an 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)} \cdot 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 $\ell$ 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 $\ell \geq m - O(\frac{\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_09009 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fixed-Parameter Algorithms for the Kneser and Schrijver Problems Haviv, Ishay Data Structures and Algorithms Combinatorics The Kneser graph $K(n,k)$ is defined for integers $n$ and $k$ with $n \geq 2k$ as the graph whose vertices are all the $k$-subsets of $[n]=\{1,2,\ldots,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 an 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)} \cdot 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 $\ell$ 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 $\ell \geq m - O(\frac{\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. |
| title | Fixed-Parameter Algorithms for the Kneser and Schrijver Problems |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2204.09009 |