It is shown that for every $\gamma=o(\frac{\log N}{\log\log N})$, $\gamma$-gap $k$-SetCover is W[1]-hard even when $d=O(k^{2}\gamma\log(k\gamma)) and $d^*=O(k\gamma)$.
Abstract
In the $\gamma$-gap $k$-SetCover problem, we are given a family $\mathcal{S}$ over a universe $U$, and the goal is to distinguish between the case where $\mathcal{S}$ contains $k$ sets covering $U$, and the case where at least $\gamma k$ sets in $\mathcal{S}$ are needed to cover $U$. We show that, for every $k^{\Omega(k^2)}\le\rho\le n^{O(1)}$, it is W[1]-hard to approximate $k$-SetCover within ratio $\Omega\big(\frac{\log\rho}{k^2\log\log\rho}\big)$ on instances with $n$ sets and universe size at most $\rho\log n$. We also show that under the randomized $k$-OV Hypothesis, there is no bounded-error randomized $f(k)n^{o(k)}$-time $o\big(\frac{\log N}{\log\log N}\big)$-approximation algorithm for $k$-SetCover. These results improve on the previous $(\log n)^{1/O(k)}$-inapproximability. For fixed $k$, this matches the polynomial-time $(\ln\rho+O(1))$-approximation up to a $\log\log\rho$ factor. We further establish a connection between small universes and large approximation gaps. We show that for every $1\le\gamma\le\min\big\{\frac{\log u}{\log\log N},\frac{\log u}{k^2\log\log u}\big\}$, exact $k$-SetCover with universe size $u^{\Theta(1/\gamma)}$ is equivalent to $\gamma$-gap $k$-SetCover with universe size $u$ under randomized Turing reductions. This suggests a barrier to proving superconstant-gap W[2]-hardness: such a result would also make exact $k$-SetCover with universe size $n^{o(1)}$ W[2]-hard under randomized FPT Turing reductions. Finally, we analyze the VC dimensions of the set systems produced by our reduction. Write $d$ and $d^*$ for the primal and dual VC dimensions respectively. We show that for $\gamma=o(\frac{\log N}{\log\log N})$, $\gamma$-gap $k$-SetCover is W[1]-hard even when $d=O(k^{2}\gamma\log(k\gamma))$ and $d^*=O(k\gamma)$. The bound for $d^*$ matches the $O(d^*\log k)$-approximation algorithm up to a $k\log k$ factor.
We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthi...
V. Guruswami, Xuan-Di Ren· Electron. Colloquium Comput....· 1 citation
We prove that every set $\mathcal{B}\subseteq\mathbb{Z}_{\ge0}$ for which $\mathbb{P}+\mathcal{B}$ contains all sufficiently large integers satisfies $B(X)\gg\log X\log\log X$, where $B(X)=\#(\mathcal{B}\cap[0,X])$ and the implied constant is absolute. This proves a quantitative form of Ruzsa's Conjecture 2 and gives a...
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, an...
Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht· 0 citations
We denote by $f_k(\Gamma)$ the largest integer with the property that every subset of a finite abelian group $\Gamma$ of size at least $|\Gamma| - f_k(\Gamma)$ is a $k$-fold sumset. Extending a recent result of Alon and Pham, we prove that $$ f_k(\Gamma) \leq \widetilde{O} \left(n^{(2k-1)/(4k-3)}\right) $$ holds for al...
Given a graph $T$ and a nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a host graph $G$. Alon and Shikhelman [Algorithmica, 2022] conjectured that if $e(T)>0$ and no member of $\mathcal{F}$ is a subgraph...
Yi-Han Chen, Jia-Lin He, Xi-He Li et al.· 1 citation· ⚡1
A $k$-configuration is a collection of $k$ distinct integers $x_{1},\ldots ,x_{k}$ together with their pairwise arithmetic means $\frac{x_{i}+x_{j}}{2}$ for $1 \leq i < j \leq k$. Building on recent work of Filmus, Hatami, Hosseini, and Kelman on binary systems of linear forms and of Kelley and Meka on Roth’s theorem...
Adrian Beker· International mathematics re...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.