论文标题
固定参数算法用于旋塞问题
A Fixed-Parameter Algorithm for the Kneser Problem
论文作者
论文摘要
neser Graph $ k（n，k）$定义为整数$ n $和$ k $，带有$ n \ geq 2k $作为图形，其顶点都是$ k $ -subsets $ \ {1,2，\ ldots，n \} $，如果有两种此类套件，则它们是相邻的。洛瓦斯（Lovász）的经典结果断言，$ k（n，k）$的色度为$ n-2k+2 $。在计算旋转问题中，我们为$ k（n，k）$带有$ n-2k+1 $颜色的顶点的颜色提供了Oracle访问，目标是找到单色边缘。我们提出了一种随机问题的随机算法，用于运行时间$ n^{o（1）} \ cdot k^{o（k）} $。这表明该问题是相对于参数$ k $的固定参数。该分析涉及相交家族和诱导的旋塞图的结构结果。 我们还研究了为一组$ m $项目分配给一组$ \ ell $ $ $ agents的一小部分的令人满意的问题，以便所有代理商对子集的重视程度至少与其补充一样多。作为我们算法在旋塞问题中的应用，我们为满足$ \ ell \ geq m-o（\ frac {\ frac {\ log m} {\ log log \ log \ log \ log \ log \ log \ log m}的实例，我们获得了一个随机的多项式时间算法，用于可符合的集合问题。我们进一步表明，可满足的问题至少与Kneser问题的变体一样困难，并扩展了对输入着色的访问。
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 $\{1,2,\ldots,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)} \cdot 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 $\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 that satisfy $\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.
