Near-Logarithmic Inapproximability of Parameterized Set Cover

arXiv:2609.19623 · cs.CC · Submitted 2026-09-17 · Read on arXiv

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

Where the paper says it

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+α).

2 assumes ETH and shows that for every computable function f, no deterministic algorithm distinguishes opt(Γ) ≤ k from opt(Γ) > kγk(n) in time f(k)Γεk, even when n = O((log m)1+α) The SETH lower bound shows that under the Strong Exponential Time Hypothesis, 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

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

Where the paper says it

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.

1

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

Where the paper says it

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.

6, which states there are absolute constants C0, η > 0 such that, for every computable function f, no deterministic algorithm solves grouped binary k-Vector Sum with D ≤ C0k log N in time f(k)Nηk

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

Where the paper says it

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].

1 The total time for calls to the hypothetical gap algorithm is at most NλN(1+τ+o(1))(k−δ) ≤ Nk−7δ/8+o(1) Since k ≥ 2 and 0 < δ < 1, λ + 1 + τ < k−δ/2

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

Where the paper says it

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].

A survey on approximation in parameterized complexity: Hardness and algorithms

[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

Where the paper says it

Organization. Section 2 defines the problems and records the source hardness statements.

[Joh74] David S. p. 0

Where the paper says it

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].

Johnson. Approximation algorithms for combinatorial problems

[KLM19] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. p. 1

Where the paper says it

[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.

On the parameterized complexity of approximating dominating set

[KN21] Karthik C. S. and Inbal Livni Navon. p. 1

Where the paper says it

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.

On hardness of approximation of parameterized set cover and label cover: Threshold graphs from error correcting codes

[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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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