Near-Logarithmic Inapproximability of Parameterized Set Cover
summary
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…
In short
This work proves that finding a small set cover is hard to approximate even with a near-logarithmic factor, specifically $k rac{ ext{log } n}{k^2 ext{ log log } n}$. It establishes this hardness under both W[1]-hardness and the Exponential Time Hypothesis (ETH), meaning no efficient deterministic algorithm can distinguish between a perfect cover of size $k$ and one significantly larger.
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 used across episodes
This episode discusses
- Near-Logarithmic Inapproximability of Parameterized Set Cover · Paper Radio
- On the Parameterized Complexity of Approximating Dominating Set
The paper
Near-Logarithmic Inapproximability of Parameterized Set Cover · Read on arXiv
Nanjing University
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game