论文标题
Kneser和Schrijver问题的固定参数算法
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
论文作者
论文摘要
neser Graph $ k（n，k）$定义为整数$ n $和$ k $，带有$ n \ geq 2k $作为图形，其顶点都是$ k $ -subsets $ [n] = \ {1,2，\ ldots，n \} $，如果有两个这样的设置在彼此相邻的情况下， Schrijver Graph $ s（n，k）$定义为$ k（n，k）$的子图，由所有$ k $ subsets的$ [n] $的集合所诱导的，这些$ [n] $不包括两个连续的元素模拟$ n $。众所周知，$ k（n，k）$和$ s（n，k）$的色度为$ n-2k+2 $。 在计算旋转和Schrijver问题中，我们可以访问$ k（n，k）$和$ s（n，k）$的$ n-2k+1 $颜色的着色，目标是找到单色边缘。我们证明，这些问题允许使用运行时间的随机算法$ n^{o（1）} \ cdot k^{o（k）} $，因此相对于参数$ k $，它们是可固定参数的。该分析涉及相交家族和诱导的kneser和Schrijver图的诱导子图的结构结果。 我们还研究了为一组$ m $项目分配给一组$ \ ell $ $ $ agents的一小部分的令人满意的问题，以便所有代理商对子集的重视程度至少与其补充一样多。作为我们算法在旋塞问题中的应用，我们为使用$ \ ell \ geq m-o（\ frac {\ frac {\ log m} {\ 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 $[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.
