Near-Logarithmic Inapproximability of Parameterized Set Cover
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Near-Logarithmic Inapproximability of Parameterized Set Cover".
Jane: Here's the gist of the paper. Near-Logarithmic Inapproximability of Parameterized Set Cover studies the approximability of Set Cover parameterized by its target cover size k and establishes a near-logarithmic hardness factor under W
1: -hardness and Exponential Time Hypothesis (ETH) The paper proves that distinguishing opt(Γ) ≤ k from opt(Γ) > k · c log n / (k squared log log n) is W
1: -hard, and under ETH, no deterministic algorithm solves this gap problem in time f(k)Γεk Hardness Results for Parameterized Set Cover The authors establish near-logarithmic inapproximability for parameterized Set Cover under both W
1: ̸= FPT and ETH Theorem 1.1 states that it is W
1: -hard to distinguish opt(Γ) ≤ k from opt(Γ) > kγk(n), where γk(n) is defined as c log n / (k squared log log n) Theorem 1.2 further shows that assuming ETH, no deterministic algorithm can distinguish these two possibilities in time f(k)Γεk The SETH lower bound proves a near-logarithmic hardness factor even when the running-time exponent is reduced from exhaustive search by only a fixed constant Reduction Framework and Gap Construction The proof begins by reducing grouped binary k-Vector Sum to Rectangular Label Cover The reduction involves a two-stage linear compression to keep the number of tests linear in the source dimension up to logarithmic factors, while the message alphabet depends only logarithmically on that dimension This construction yields an instance where list-val(I) = k for YES instances and list-val(I) > h for NO instances The final reduction from Rectangular Label Cover to Set Cover produces a gap where opt(Γ) ≤ k if the source is a YES instance, and opt(Γ) > c log B / (k log log B) if the source is a NO instance Bounding the Approximation Gap Lemma 4.4 provides a construction for an instance with exactly N indexed sets and exactly B universe elements such that if the source is YES, then opt(Γ) ≤ k, and if NO, then opt(Γ) > c log B / (k log log B) The analysis shows that the universe size U0 can be bounded by B, which is related to the budget assumption (log N)1+a ≤ B ≤ Nb This leads to the final gap bound h/k = Ωα log B / (k squared log log B) Establishing the SETH Lower Bound The SETH lower bound is proven by applying the local acceptance construction to a communication protocol for disjointness This involves repeating the protocol O(k log h) times with the same advice, and using an OR reduction over advice strings to establish a deterministic time lower bound The final result shows that both contributions are O(Nk−δ/2), contradicting Lemma 5.1 The construction time is bounded by Nλ+1+τ+o(1) where t = ⌈k log2 h⌉ + 1 Since k ≥ 2 and 0 < δ < 1, λ + 1 + τ < k − δ/2, which contradicts the lower bound derived from Lemma 5.1 The paper concludes that the near-logarithmic approximation gap persists even under strong exponential time hypotheses and for running times close to exhaustive search Source Hardness for Grouped Binary Vector Sum The hardness results for the source problem are established by showing that grouped binary k-Vector Sum is W
1: -hard even when D ≤ C0k log N Furthermore, under ETH, there is no deterministic algorithm solving it in time f(k)Nηk for any computable function f The proof utilizes a construction based on an r-Clique instance to show W
1: -hardness and a partitioning of variables into r groups to establish the ETH exponent bound The total number of vectors N satisfies D = O(K log N) with an absolute constant ETH Exponent Proof The proof for the ETH exponent relies on partitioning variables into r groups and clauses into r groups whose sizes differ by at most one The sum of vectors is zero exactly when the clause witness agrees with the global variable assignment at that occurrence This structure ensures a zero-sum selection exists if and only if the 3CNF formula is satisfiable The total number of vectors N satisfies ⌊M/r⌋ ≤ N ≤ r 2⌈3M/r⌉ + r7⌈M/r⌉ ≤ 2r 23⌈M/r⌉ The construction time is 2O(M/r) poly(M, r) ETH Exponent Proof The proof for the ETH exponent relies on partitioning variables into r groups and clauses into r groups whose sizes differ by at most one The sum of vectors is zero exactly when the clause witness agrees with the global variable assignment at that occurrence This structure ensures a zero-sum selection exists if and only if the 3CNF formula is satisfiable The total number of vectors N satisfies D = O(k log N) with an absolute constant The construction time is 2O(M/r) poly(M, r) ETH Exponent Proof
Title and authors: Jane: So, how do they actually prove this hardness? What's the core idea behind this proof for the reader who doesn't read math?
Tom: They start by taking a problem called grouped binary k-Vector Sum and reducing it to a problem called Rectangular Label Cover. This reduction has some clever steps, involving two linear compressions, so the number of tests stays manageable.
Lu: The reduction is designed specifically so that for YES instances, the optimal cover size is exactly k, but for NO instances, it’s much bigger than k times c log n over k squared log log n > Page two of THIS PAPER <ref:2609.19623#pg1>.
Jane: So they build a scenario where if the answer is yes, you can find a cover of size k. If it's no, you have to find one that is at least this much larger than k times that specific logarithmic factor.
Meng: That specific function c log n over k squared log log n means the required size for a bad solution grows quite fast with the universe size n and how small your allowed cover size k is > Page one of THIS PAPER <ref:2609.19623#pg1>.
Tom: The paper then moves from that label cover problem to Set Cover, creating this gap where opt of Gamma is less than or equal to k if it’s a YES instance, but greater than c log B over k log log B if it’s a NO instance > Page two of THIS PAPER <ref:2609.19623#pg1>.
The paper's summary: Jane: The authors suggest some improvements to this approach, and they show that this near-logarithmic gap is actually better than what we can achieve in practice for small cover sizes.
Tom: They point out that even under the Strong Exponential Time Hypothesis, which is a stronger assumption than ETH, no deterministic algorithm can solve this gap problem in time f of k times n minus delta over two > Page one of THIS PAPER <ref:2609.19623#pg1,under the Strong Exponential Time Hypothesis>.
Lu: That means they rule out an approximation factor smaller than log n over log log n under SETH, meaning even if you reduce the running time from exhaustive search by just a fixed constant, you still get that near-logarithmic hardness factor > Page three of THIS PAPER.
Meng: That implies that for small k, we can’t expect to find an approximation better than this specific gap factor in any deterministic time f of k times epsilon over k under ETH > Page two of THIS PAPER <ref:2609.19623#pg1>.
Lalam: The paper also provides a way to construct these Set Cover instances where the universe size is bounded by B, and B can be chosen as B of N equals log (ceil(log N plus one) plus alpha) m > Page one of THIS PAPER <ref:2609.19623#pg1>.
The paper's improvements: Tom: So, to wrap up the "Near-Logarithmic Inapproximability of Parameterized Set Cover," it confirms that we can’t get much better than this specific gap factor for Set Cover parameterized by k, even assuming ETH holds > Page one of THIS PAPER <ref:2609.19623#pg1,Near-Logarithmic Inapproximability of Parameterized Set Cover>.
Jane: It means if you are trying to find a small cover, the best deterministic approximation you can hope for is still within a constant factor of the greedy algorithm’s ratio when n gets really big > Page two of THIS PAPER <ref:2609.19623#pg1,factor of the greedy algorithm’s>.
Lu: The paper shows that this hardness persists even under SETH, meaning it’s not just about how much time we allow an algorithm to run, but the fundamental structure of the problem itself is hard > Page three of THIS PAPER.
Meng: From an engineering standpoint, this tells us that for practical applications where k is small, we need to be realistic about the approximation quality we can expect without changing our underlying complexity assumptions > Page two of THIS PAPER <ref:2609.19623#pg1>.
Lalam: The core finding is that the gap remains near-logarithmic even when you reduce the running time exponent from exhaustive search by only a fixed constant, showing this hardness factor stays solid > Page one of THIS PAPER <ref:2609.19623#pg1,from exhaustive search by only a fixed constant>.
Conclusion: Tom: So we’ve been talking about "Near-Logarithmic Inapproximability of Parameterized Set Cover," and the main takeaway is that for small cover sizes k, we can't get much better than this specific gap factor > Page one of THIS PAPER.
Jane: Exactly. We're looking at parameterised Set Cover, which is a classic problem where you want to find the smallest set of sets that covers everything, and this paper proves that distinguishing between finding an optimal cover of size k and something significantly larger is hard > Page two of THIS PAPER.
Lu: The core idea behind the proof involves reducing grouped binary k-Vector Sum to Rectangular Label Cover, which is a pretty complex way to set up the test cases for this problem > Page two of THIS PAPER.
Meng: From an engineering view, it means that if you're trying to deploy a model where you need a small number of components to cover all your data points, you can’t expect an approximation ratio smaller than this log n over k squared log log n unless you change the fundamental assumptions about how much time your system can afford > Page three of THIS PAPER.
Lalam: I'm confident in this result. The analysis shows that even under the Strong Exponential Time Hypothesis, which is a stronger assumption than ETH, no deterministic algorithm can solve this gap problem in time f of k times n minus delta over two > Page one of THIS PAPER.
Jane: That’s a big statement for us to take away. It means we can't just rely on an algorithm magically finding a near-optimal solution faster than this log factor, even if the running time is slightly reduced > Page two of THIS PAPER.
Tom: So what does that mean for the world? If you’re dealing with massive datasets where you need to cover things efficiently, this tells us that the difficulty isn't just in finding a good heuristic; it’s baked into the problem structure itself > Page three of THIS PAPER.
Lu: It suggests that for problems like Set Cover, we have to accept certain limits on approximation quality unless we fundamentally change how we define what kind of complexity class we are working within > Page one of THIS PAPER.
Meng: For production systems, it means you shouldn't spend all your time trying to beat this gap with tiny algorithmic tweaks; the structure dictates a certain ceiling for performance > Page two of THIS PAPER.
Lalam: I’m sure it's true because the construction itself is so precise, showing exactly how the universe size B relates to N and k in a way that locks in that lower bound > Page one of THIS PAPER.
Jane: It’s a very detailed look at where we stand with this problem, but it opens up new avenues for looking at these parameterised problems through the lens of complexity theory > Page two of THIS PAPER.
Tom: Yeah, definitely something to keep an eye on as we move into designing more robust systems > Page three of THIS PAPER.
Nanjing University
cs.CC
Submitted: 2026-09-17
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: Near-Logarithmic Inapproximability of Parameterized Set Cover studies the approximability of Set Cover parameterized by the target cover size k and proves that distinguishing opt(Γ) ≤ k from…
Key concepts
- Parameterized Set Cover
- This is a problem where you are given a collection of sets, and you want to find the smallest number of these sets needed to cover all elements in a universe. The 'parameterized' aspect means we analyze how hard this becomes when the desired cover size $k$ is small.
- W[1]-hardness
- This complexity class indicates that the problem is likely much harder than problems solvable in polynomial time, even when restricted by a parameter $k$. Proving W[1]-hardness shows that finding an exact or near-exact solution for small $k$ is computationally intractable.
- Exponential Time Hypothesis (ETH)
- ETH is a major complexity assumption stating that certain problems cannot be solved in time significantly faster than exponential time, even with a constant factor. Using ETH allows the authors to show that approximating Set Cover within a specific gap requires super-polynomial time relative to $k$.
Terminology
Summary
Near-Logarithmic Inapproximability of Parameterized Set Cover studies the approximability of Set Cover parameterized by the target cover size k and proves that distinguishing opt(Γ) ≤ k from opt(Γ) > k · c log n / (k squared log log n) is W[1]-hard under an Exponential Time Hypothesis
Hardness Results
The paper establishes near-logarithmic inapproximability for parameterized Set Cover under both W[1] ̸= FPT and ETH Theorem 1.1 states that for every fixed α > 0, there is a constant c = c(α) > 0 such that it is W[1]-hard, parameterized by k, to distinguish opt(Γ) ≤ k from opt(Γ) > kγk(n), where γk(n):= c log n / (k squared log log n) This holds even for instances with m indexed sets and a universe of size n = O((log m)1+α) Theorem 1. p. 2 For every fixed α > 0, there is a constant c = c(α) > 0 such that it
is W[1]-hard, parameterized by k, to distinguish
opt(Γ) ≤ k from opt(Γ) > kγk(n). This holds even for instances with m indexed sets and a universe of size n = O((log m)
1+α).Where the paper says it
Reduction Framework
The proof relies on a reduction from grouped binary k-Vector Sum to Rectangular Label Cover The source problem is transformed into a decision problem where the goal is to find vectors xi ∈ Xi such that Pk i=1 xi = 0 This grouped binary k-Vector Sum instance is then reduced to a k-RectLabelCover instance, which involves label groups W, tests V, and message alphabet Σ The reduction uses a (D, d, A)-linear separator to construct the RectLabelCover instance where V = H and Σ = 2d
Gap Construction
The core of the inapproximability proof involves constructing a gap in the RectLabelCover instance Lemma 4.4 shows that for a grouped binary k-Vector Sum instance with N:= Pk i=1 Xi ≥ N0(k), D ≤ C0k log N, and an integer budget (log N)1+α ≤ B ≤ Nb, one can construct in time NC a Set Cover instance Γ with exactly N indexed sets and exactly B universe elements such that if the source is a YES instance, then opt(Γ) ≤ k; if the source is a NO instance, then opt(Γ) > c log B/(k log log B) This construction yields a gap of h/k = Ωα / (log B / (k squared log log B))
Set Cover Mapping
The final step maps the gap in RectLabelCover to a Set Cover instance Lemma 4.3 shows there is an algorithm that outputs a Set Cover instance Γ = (S, U) such that if list-val(I) = k, then opt(Γ) ≤ k; if list-val(I) > h, then opt(Γ) > h The universe size bound is U ≤ V(kΣ + 1)h This leads to the final bound on the universe size, log U0 ≤ log B
ETH Lower Bound Proof
The SETH lower bound is established by applying the local acceptance construction to a communication protocol for disjointness Lemma 5.1 provides the SETH hardness of disjointness selection, showing that for every fixed integer k ≥ 2 and constant ξ ∈ (0, 1), there is a constant C0 such that disjointness selection with D ≤ C0 log N has no deterministic O(Nk−ξ)-time algorithm The repetition and list soundness arguments then lead to the conclusion that both contributions are O(Nk−δ/2), contradicting Lemma 5. p. 2 Assume SETH. For every fixed integer k ≥ 2 and fixed constant
δ > 0, there are constants η = η(k, δ) > 0 and n0 = n0(k, δ) such that no deterministic algorithm
distinguishes
opt(Γ) ≤ k from opt(Γ) > kη log n
log log n
in time O(|Γ|
k−δ
) on instances with universe size n = |U| ≥ n0.Where the paper says it
Source Hardness for Vector Sum
The source hardness for grouped binary Vector Sum is established by showing that it is W[1]-hard even when D ≤ C0k log N Lemma 2.5 proves this, stating there is an absolute constant C0 such that grouped binary k-Vector Sum is W[1]-hard even when D ≤ C0k log N The ETH hardness for the source problem follows from Lemma 2. p. 6 They are consistent with the established hardness
of sparse linear systems [BGGS16, BIWX11]. There is an absolute constant C0 such that grouped binary k-Vector Sum is W[1]-hard
even when D ≤ C0k log N.Where the paper says it
ETH Exponent Hardness
The proof of Lemma 2.6 demonstrates the ETH hardness for the source problem, showing that if an algorithm existed for some computable f, even only for even parameters above a fixed threshold, it would contradict ETH The construction time is 2O(M/r) poly(M, r), and we have log N ≤ 6M/k + O(log k + 1)
Final Approximation Factor
The final approximation factor derived from the analysis is kη log n / log log n ≤ h/2 This implies that the YES outputs satisfy opt ≤ k, and every NO output satisfies the NO promise of Theorem 1.3 The total time for calls to the hypothetical gap algorithm is at most NλN(1+τ+o(1))(k−δ) ≤ Nk−7δ/8+o(1) All instance constructions together take Nλ+1+τ+o(1) time
Source Hardness for Disjointness
The protocol of Lemma 5.2 uses algebraic geometric codes, and the resulting Set Cover instance has explicit bit length Γµ = O(kNn log(kNn)) ≤ N1+τ+o(1) The construction time is bounded by the same bound as its explicit length This confirms that the resulting instance is constructed within the same bound as its explicit length
Parameter Control
The parameter control is essential for the W[1] and ETH results below The construction time is polynomial in the explicit input, separator, and output lengths Smaller instances are handled in FPT time
Instance Padding
The universe U0 is nonempty because the empty message collection is rejecting Duplicate an element until its size is exactly n = ⌈Nτ⌉, preserving the optimum The resulting instance Γµ has explicit bit length Γµ = O(kNn log(kNn)) ≤ N1+τ+o(1)
Running Time Bound
The running time bound is O(Nk−δ/2), contradicting Lemma 5.1 Both contributions are O(Nk−δ/2), contradicting Lemma 5. p. 5 The assumption W[1] ̸= FPT implies that
parameterized Clique has no FPT algorithm. We use the following clause-count formulation of ETH, which is equivalent to the usual variablecount formulation by the sparsification lemma [IPZ01].Where the paper says it
ETH Exponent Bound
The ETH exponent bound is established by showing that if an algorithm existed for some computable f, even only for even parameters above a fixed threshold, it would contradict ETH The construction and solution together take at most O(2δM/2) time This proves the strengthened statement
Final Gap Claim
The final gap claim is h ≥ τL / 32k2(l0 + 1) log2 L, log2 n / log2 log2 n ≤ 4τL/log2 L This proves the gap claim The YES outputs satisfy opt ≤ k, and every NO output satisfies the NO promise of Theorem 1.3
Final Conclusion
The paper concludes that both contributions are O(Nk−δ/2), contradicting Lemma 5.1 This proves the theorem The parameter k and the exponent saving δ are fixed before N tends to infinity The argument uses an OR reduction over advice strings and establishes a deterministic time lower bound; it does not require a parameter-preserving many-one reduction from SAT The paper is 2609.19623.
References
[AMS06] Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions
[AS03] Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications
[BGGS16] Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. On the Hardness of Learning Sparse Parities
[BIWX11] Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, and Ning Xie. The Complexity of Linear Dependence Problems in Vector Spaces
[CCK+20] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, dominating set, and more
[Chv79] Vašek Chvátal. A greedy heuristic for the set-covering problem
[CL19] Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem
[DS14] Irit Dinur and David Steurer. Analytical approach to parallel repetition
[Fei98] Uriel Feige. A threshold of ln n for approximating set cover
[FKLM20] Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. p. 1 The
remaining issue is the running time. The goal of determining this tradeoff is also emphasized in the survey of Feldmann, Karthik,
Lee, and Manurangsi [FKLM20].Where the paper says it
[GOS20] Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting alphabet reduction in Dinur’s PCP
[GR26] Venkatesan Guruswami and Xuandi Ren. Almost optimal FPT inapproximability for k-SetCover
[IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? p. 5 Organization. Section 2 defines the problems and records the source hardness statements.Where the paper says it
[Joh74] David S. p. 0 The polynomial-time approximability of Set Cover is well understood. The greedy algorithm
achieves approximation ratio Hn ≤ 1 + ln n [Joh74, Lov75, Chv79], and its worst-case ratio is
ln n − ln ln n + Θ(1) [Sla97].Where the paper says it
[KLM19] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. p. 1 [CCK+20] ruled out
every approximation factor depending only on k under Gap-ETH. Karthik, Laekhanukit, and
Manurangsi [KLM19] obtained this conclusion under W[1] ̸= FPT and proved f(k)|Γ|
o(k)
-time
inapproximability under ETH.Where the paper says it
[KN21] Karthik C. S. and Inbal Livni Navon. p. 1 Here the approximation factor is c0
k
(log n/ log log n)
1/k
. 1 Karthik
and Livni-Navon [KN21] subsequently gave a general construction of threshold graphs from errorcorrecting codes and identified a limitation of the existing composition that keeps the gap at a
parameter-dependent root of the logarithm.Where the paper says it
[Lin19] Bingkai Lin. A simple gap-producing reduction for the parameterized set cover problem
[Lov75] László Lovász. On the ratio of optimal integral and fractional covers
[LRSW23] Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. Constant approximating parameterized k-SetCover is W[2]-hard
[LY94] Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems
[Mos15] Dana Moshkovitz. The projection games conjecture and the NP-hardness of ln napproximating Set-Cover
[RS97] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
[Sla97] Petr Slavík.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Faster approximation of Set Cover for small target sizes: The algorithm can distinguish opt(Gamma) k gamma k(n) where gamma k(n) = c log n / (k squared log log n), which is a near-logarithmic gap, providing a stronger guarantee than the greedy algorithm's ratio of 1 + ln n.
-
Improved running time for parameter-specific approximation: For fixed k, there is no deterministic algorithm that solves the gap problem in time f(k)Gamma epsilon k, even under the Exponential Time Hypothesis (ETH), which implies that algorithms for small covers can achieve an o(log n) approximation in time f(k)Gamma o(k).
-
Hardness against faster exponential time algorithms: Under the Strong Exponential Time Hypothesis (SETH), no deterministic algorithm solves the gap problem in time O(Gamma k - delta) for every fixed k >= 2 and delta > 0, meaning even reducing the exponent from exhaustive search by only a fixed constant still yields a near-logarithmic hardness factor.
-
Efficient construction of Set Cover instances: The paper provides a reduction that constructs Set Cover instances where the universe size is bounded by B, which can be chosen as B(N) = log (ceil(log N) + 1) a m, ensuring the constructed instance has exactly N indexed sets and a universe of size n = B(N), allowing for precise control over the approximation gap.
-
Optimized verification of Set Cover solutions: The reduction from k-RectLabelCover to Set Cover allows verifying if a labeling covers every test by checking if
S1,lambda1, . . . , Sk,lambdak cover U,
which is guaranteed to be true if a single labeling covers every test and false otherwise.
Abstract
In the γ-gap k-SetCover problem, we are given a family S over a universe U, and the goal is to distinguish between the case where S contains k sets covering U, and the case where at least γk sets in S are needed to cover U. We show that, for every k Ω(k 2) at mostρ at most n O(1), it is W[1]-hard to approximate k-SetCover within ratio Ω (ρ over k 2 ρ) on instances with n sets and universe size at most ρ n. We also show that under the randomized k-OV Hypothesis, there is no bounded-error randomized f(k)n o(k) -time o (N over N) -approximation algorithm for k-SetCover. These results improve on the previous (n) 1/O(k) -inapproximability. For fixed k, this matches the polynomial-time (ρ+O(1)) -approximation up to a ρ factor. We further establish a connection between small universes and large approximation gaps. We show that for every 1 at mostγ at most u over N, u over k squared u, exact k-SetCover with universe size u Θ(1/γ) is equivalent to γ-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 γ=o(N over N), γ-gap k-SetCover is W[1]-hard even when d=O(k squaredγ (kγ)) and d*=O(kγ). The bound for d* matches the O(d* k) -approximation algorithm up to a k k factor.
Sources
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?