论文标题
关于参数化集盖和标签盖的近似值的硬度：错误校正代码的阈值图
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes
论文作者
论文摘要
In the $(k,h)$-SetCover problem, we are given a collection $\mathcal{S}$ of sets over a universe $U$, and the goal is to distinguish between the case that $\mathcal{S}$ contains $k$ sets which cover $U$, from the case that at least $h$ sets in $\mathcal{S}$ are needed to cover $U$. Lin（ICALP'19）最近显示了一个差距，从$（K，K+1）$ - setCover问题的大小$ o_k（\ log | \ mathcal {s} |）$ setCover问题到$ \ left（k，\ sqrt [k] {k，sqrt [k] { | \ Mathcal {s} |}}} \ cdot k \ right）$ - 大小$ | \ Mathcal {s} | $的setCover问题。在本文中，我们证明了他的结果的更可扩展版本：鉴于任何错误纠正代码$ c $ ablphabet $ [q] $，速率$ρ$和相对距离$δ$，我们使用$ c $从$（k，k，k+1）$ - setCover $ setcover y-setcover y-setcover resse $ $ $ $ unive u $ $ unive u $ $ u $ y to the Universe u $ y to the the the the the the the the the the the the the the Universe $ $ $ \ left（k，\ sqrt [2k] {\ frac {2} {1-Δ}} \ right）$ - setCover问题$ \ frac {\ frac {\ frac {\ log | \ mathcal {s} s} |} |} |}ρ\ cdot | cdot | u |^^{q^k^k} $。 林通过用特殊的阈值图组成输入setCover实例（没有差距）来建立他的结果，该实例是由极端组合对象构成的特殊阈值图，称为通用集合，从而带来了带有GAP的最终setCover实例。我们的还原遵循完全相同的行，只是我们仅使用错误校正代码$ c $的基本属性生成Lin指定的阈值图。 我们使用上面提到的相同阈值图来证明在W [1] $ \ neq $ fpt和ETH下，对于Chalermsook等引入的$ K $ -MAXCOVER问题。 （Sicomp'20）。我们的不Ximaiblity结果与Karthik等人获得的边界相匹配。 （JACM'19），尽管它们的证明框架截然不同，并且涉及分布式PCP框架的概括。在这项工作之前，尚不清楚如何采用林的证明策略来证明$ k $ -maxcover的不合适性结果。
In the $(k,h)$-SetCover problem, we are given a collection $\mathcal{S}$ of sets over a universe $U$, and the goal is to distinguish between the case that $\mathcal{S}$ contains $k$ sets which cover $U$, from the case that at least $h$ sets in $\mathcal{S}$ are needed to cover $U$. Lin (ICALP'19) recently showed a gap creating reduction from the $(k,k+1)$-SetCover problem on universe of size $O_k(\log |\mathcal{S}|)$ to the $\left(k,\sqrt[k]{\frac{\log|\mathcal{S}|}{\log\log |\mathcal{S}|}}\cdot k\right)$-SetCover problem on universe of size $|\mathcal{S}|$. In this paper, we prove a more scalable version of his result: given any error correcting code $C$ over alphabet $[q]$, rate $ρ$, and relative distance $δ$, we use $C$ to create a reduction from the $(k,k+1)$-SetCover problem on universe $U$ to the $\left(k,\sqrt[2k]{\frac{2}{1-δ}}\right)$-SetCover problem on universe of size $\frac{\log|\mathcal{S}|}ρ\cdot|U|^{q^k}$. Lin established his result by composing the input SetCover instance (that has no gap) with a special threshold graph constructed from extremal combinatorial object called universal sets, resulting in a final SetCover instance with gap. Our reduction follows along the exact same lines, except that we generate the threshold graphs specified by Lin simply using the basic properties of the error correcting code $C$. We use the same threshold graphs mentioned above to prove inapproximability results, under W[1]$\neq$FPT and ETH, for the $k$-MaxCover problem introduced by Chalermsook et al. (SICOMP'20). Our inapproximaiblity results match the bounds obtained by Karthik et al. (JACM'19), although their proof framework is very different, and involves generalization of the distributed PCP framework. Prior to this work, it was not clear how to adopt the proof strategy of Lin to prove inapproximability results for $k$-MaxCover.
