PaperlayerView exact revision on arXiv

Source-linked AI summary

A Near-Linear Element Kernel for \(d\)-Hitting Set

Zimo Sheng, Mingyu Xiao

arXiv:2609.06512v1cs.DScs.CC

TL;DR

Whether d-Hitting Set can improve on the O(k^(d−1)) element bound by a polynomial factor has remained an open question. The paper re-encodes selected solution elements with shared Boolean variables and CNF constraints, using hashing to reduce the number of variables. For every fixed d ≥3, d-Hitting Set admits a one-sided randomized kernel with O(k log^3 k) elements and success probability at least 3/4.

  • Problem

    Whether d-Hitting Set can improve on the O(k^(d−1)) element bound by a polynomial factor has remained an open question.

    Source: §1 · p. 1

  • Method

    The paper re-encodes selected solution elements with shared Boolean variables and CNF constraints, using hashing to reduce the number of variables.

    Source: §1 · p. 2, §1.2 · p. 3

  • Results

    For every fixed d ≥3, d-Hitting Set admits a one-sided randomized kernel with O(k log^3 k) elements and success probability at least 3/4.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The results provide near-linear element bounds for the randomized kernel and a quadratic-logarithmic bound for the deterministic kernel.

    Source: §1.1 · p. 2, §6 · p. 20

    Stronger candidate bounds described by the authors remain unchecked and are not included in the paper.

    Source: Statement on the Use of Generative AI · p. 21

Abstract

from arXiv · show

In \(d\)-\textsc{Hitting Set}, the input consists of a finite universe \(U\), a family \(\mathcal S\) of subsets of \(U\) with size at most \(d\), and an integer \(k\). The task is to decide whether at most \(k\) elements of \(U\) can intersect every set in \(\mathcal S\). For every fixed \(d\geq3\), we give a one-sided randomized kernel with \(O(k\log^3k)\) elements and a deterministic kernel with \(O(k^2\log k)\) elements for \(d\)-\textsc{Hitting Set}. In the one-sided randomized kernel, every NO-instance is always mapped to a NO-instance, and a YES-instance is mapped to a YES-instance with constant probability. The previously known kernels for \(d\)-\textsc{Hitting Set} contain \(O(k^{d-1})\) elements and \(O(k^d)\) sets. It has been asked in the literature whether \(d\)-\textsc{Hitting Set} allows kernels with \(O(k^{d-1-\varepsilon})\) elements for some constant \(\varepsilon>0\). In this paper, we answer this question affirmatively by giving near-linear element-kernels through a re-encoding of the instance. On the other hand, our kernel may still contain \(k^{O(d)}\) sets and the parameter $k$ may grow polynomially.

1 Introduction

The paper asks whether the element bound for d-Hitting Set can be improved beyond prior kernels and presents a hash-based re-encoding to reduce the number of elements. For every fixed d≥3, it gives randomized and deterministic kernels with improved element bounds.

1 Introduction

  • Earlier kernels used O(k^(d−1)) elements and O(k^d) sets; whether the element exponent could be reduced by a polynomial factor remained open.A central formulation asks whether the element-bound degree can be made independent of fixed rank d.Source: §1 · p. 1

1.1 Results

  • For fixed d≥3, randomized kernels use O(k log^3 k) elements with success probability at least 3/4, while deterministic kernels use O(k^2 log k) elements.The randomized theorem also bounds its output parameter by O(k log^3 k).Source: §1.1 · p. 2

1.2 Technical Overview

  • The kernelization first reduces the instance, encodes it as a width-at-most-d CNF formula, then transforms that formula back into d-Hitting Set.The compact Boolean encoding is the main contribution; the first and third steps are standard.Source: §1.2 · p. 2
  • A maximal family of disjoint input sets either proves NO when it has more than k sets or gives O(k) elements for direct representation.Maximality ensures every input set contains one of those elements, leaving at most d−1 other elements to encode.Source: §1.2 · p. 3
  • The randomized construction uses two-level hashing and a shared table that need only distinguish the at most k elements in a solution.Every satisfying assignment decodes to a genuine hitting set, even when the sampled hash functions fail to distinguish a solution.Source: §1.2 · p. 3
  • The deterministic construction finds O(k^2) elements so every input set contains at least two, enabling shared pair variables alongside hash-selection literals.Low-degree polynomials over a finite field provide its explicit hash family.Source: §1.2 · p. 3

2 Preliminaries

This section fixes the rank-bounded hitting-set and kernel notions, distinguishes subhypergraph kernels from other outputs, and gives a linear-size CNF encoding for cardinality constraints.

2 Preliminaries

  • A d-Hitting Set instance has sets of size at most d and asks whether at most k universe elements intersect every set.A set system has rank at most d when each set has size at most d.Source: §2 · p. 4

2.1 Kernelization

  • A kernel is a polynomial-time reduction to an equivalent instance whose size and parameter are bounded by a computable function of k.A known parameter-preserving kernel has O_d(k^(d−1)) elements and O_d(k^d) sets.Source: §2.1 · p. 4
  • A one-sided randomized kernel runs in expected polynomial time, always preserves NO answers, and preserves YES answers with a stated success probability.The output-size guarantee is the same as for a kernel.Source: §2.1 · p. 4

2.2 Subhypergraph Kernels

  • A subhypergraph kernel deletes only elements and whole sets; an induced kernel additionally retains every input set contained in its retained universe.Source: §2.2 · p. 4
  • Unless coNP ⊆ NP/poly, no deterministic d-Hitting Set kernel with O(k^(d−1−ε)) elements can output a subhypergraph, for fixed d ≥ 3.The proof gives each set a private element, so retaining sets requires retaining those elements; the resulting bit compression conflicts with Dell and van Melkebeek’s lower bound.Source: §2.2 · pp. 4–5

2.3 CNF Formulas and Cardinality Constraints

  • Cardinality constraints on N Boolean variables can be encoded in polynomial time using O(N + 1) auxiliary variables and clauses of width at most three.The encoding preserves assignments satisfying the constraint, and the paper uses a parallel binary counter to convert such conditions into CNF.Source: §2.3 · p. 5

3 Hash-Based Kernel

The kernel encodes selected elements directly and represents the rest through two-level hashing and a shared table, using a CNF encoding of the budget and hitting constraints before transforming back into d-Hitting Set. Its output has O_d(k^(d-1)) elements and O_d(k^d) sets, and the construction takes expected polynomial time.

3 Hash-Based Kernel

  • Two-level hashing and a shared table let many universe elements share a Boolean representation, distinguishing only selected elements that occur together in a small solution.The first hash assigns buckets; a bucket-specific second-level hash and a short address identify the represented element.Source: §3 · p. 6

3.1 The Packing

  • A maximal packing of more than k pairwise-disjoint input sets certifies a NO-instance; otherwise, its at-most-k sets identify a set X of at most dk elements represented directly.Every input set intersects X, so each contains at most d − 1 elements from the remaining universe W.Source: §3.1 · p. 6

3.2 Two-Level Hashing

  • If a pair of hash objects separates T in two levels, a suitable map σ makes Hσ injective on T.The first-level hash separates different buckets, and the selected second-level function separates elements within each bucket.Source: §3.2 · p. 7

3.3 Representing Elements

  • For any fixed σ and assignment, at most one element mapped to a given table entry satisfies its representation test Dσ,v.Elements sharing an entry have distinct addresses, so the entry’s stored address can match at most one of them.Source: §3.3 · p. 8

3.4 The CNF Encoding

  • The CNF encoding enforces the selection budget and hitting constraints with clauses of width at most d, without enumerating all global maps σ.Each input set depends only on second-level choices for the first-level buckets it meets, so the construction imposes constraints for local maps.Source: §3.4 · pp. 8–9

3.5 Correctness

  • The CNF formula is satisfiable exactly when the input has a size-at-most-k hitting set whose elements in W are injectively represented by Hσ for some map σ.The encoding constrains the selection budget and hitting conditions while considering only local second-level choices relevant to each input set.Source: §3.4 · p. 9, §3.5 · p. 10

3.6 Reducing Back to d-Hitting Set

  • A width-at-most-d CNF with N variables and M clauses reduces in linear time to an equivalent rank-d Hitting Set instance with 2N elements, at most N + M sets, and budget N.The construction uses a pair of elements and a pair set per variable, plus at most one set per clause.Source: §3.6 · pp. 10–11

3.7 Kernel Bound

  • Under the stated sampling assumption, d-Hitting Set has a one-sided randomized kernel with success probability at least p: YES-instances are preserved with probability at least p, and NO-instances never become YES-instances.The theorem assumes fixed d ≥ 3, polynomially bounded parameters, and expected-polynomial-time sampling from the specified two-level separating distribution.Source: §3.7 · p. 12
  • The output has O_d(k^(d-1)) elements and O_d(k^d) sets.Source: §3.7 · p. 12
  • Sampling the hash objects, constructing ΦF, and applying Lemma 3.5 take expected polynomial time.Source: §3.7 · p. 12

4 Random Hashing and the Randomized Kernel

The section uses two-level hashing to encode a fixed small solution while keeping its elements distinguishable. This yields a one-sided randomized kernel whose required sampling event succeeds with probability at least 3/4.

4 Random Hashing and the Randomized Kernel

  • Two-level hashing first spreads solution elements across buckets, then supplies a second-level hash that separates the elements within each bucket.The formula chooses an available separating hash for each bucket.Source: §4 · p. 12
  • The required sampling event succeeds with probability at least 3/4, and failed encoding cannot create a false hitting set.Every satisfying assignment still decodes to a valid solution, giving the kernel its one-sided error.Source: §4 · p. 12, §4.2 · p. 14

4.1 A Random Two-Level Separating Distribution

  • With probability at least 7/8, every first-level bucket contains at most b elements of the fixed solution; conditioned on that load bound, separation succeeds with probability at least 7/8.Together, the two events give probability 49/64, which exceeds 3/4, for each fixed set T of size at most k.Source: §4.1 · pp. 13–14

4.2 The Randomized Kernel

  • The randomized construction yields output parameter k′ = O_d(k log^3 k) and runs in expected polynomial time.Source: §4.2 · pp. 14–15

5 Deterministic Hashing and Deterministic Kernel

The deterministic kernel re-encodes a solution through hashing and a bounded-width CNF formula. Its construction uses a small common set, an explicit perfect hash family, and a shared row–address representation to obtain an equivalent instance with O(k^2 log k) elements.

5 Deterministic Hashing and Deterministic Kernel

  • The encoding combines an explicit perfect hash family with a small set meeting every input set in at least two elements, preserving clause width at most d.A shared pair variable records whether either element of a designated pair is selected; the remaining elements use the shared row–address table.Source: §5 · p. 15, §5.3 · p. 18

5.1 A Small Set Meeting Every Input Set Twice

  • The preprocessing produces a set C of O(k^2) elements containing at least two elements from every input set, with only O(k^2) distinct assigned pairs.Each input set receives a designated pair contained in both that set and C.Source: §5.1 · p. 15

5.2 An Explicit Perfect Hash Family

  • A deterministic polynomial-time construction gives a k-perfect family with q and t both O(k^2), so some hash function is injective on every set of at most k elements.The family’s defining guarantee is that for each such set, at least one family function is injective on it.Source: §5.2 · p. 17

5.3 The Deterministic CNF Encoding

  • The deterministic CNF formula has clause width at most d and encodes the hitting conditions using the selected hash branch and designated-pair variables.The pair variable replaces two direct-selection literals, while the row–address representation is shared across hash branches.Source: §5 · p. 15, §5.3 · p. 18

5.4 Correctness

  • The formula is satisfiable if and only if the instance has a hitting set of size at most k.The proof decodes a satisfying assignment into selected elements that hit every input set.Source: §5.4 · p. 19

5.5 The Kernel Bound and Running Time

  • The deterministic kernel has O(k^2 log k) elements and is constructible in deterministic polynomial time.The output parameter is also O(k^2 log k).Source: §5.5 · p. 19
  • For fixed d, the cited bound is L = O_d(log k).Source: §5.5 · p. 19

6 Conclusion

The paper resolves a longstanding question about improving the element bound for d-Hitting Set by re-encoding solutions in a compact Boolean representation. This yields significantly improved element-kernels, while potentially increasing the number of sets and the output parameter.

6 Conclusion

  • The paper reports significantly improved element-kernels for d-Hitting Set, resolving a longstanding open problem in kernelization.Source: §6 · p. 20
  • The method re-encodes solution elements through shared Boolean variables and CNF clauses, then transforms the formula back into a d-Hitting Set instance.The randomized construction uses two-level hashing and short addresses; the deterministic construction uses an explicit perfect hash family and a small set meeting every input set twice.Source: §6 · p. 20
  • The compressed representation reduces output elements but may increase the number of sets and the parameter k′.The authors suggest the encoding framework may also help improve element-kernels for other problems.Source: §6 · p. 20

Statement on the Use of Generative AI

The authors describe using GPT-5.6 Sol interactively to simplify part of the encoding. They distinguish those discussions from their own review and responsibility for the paper’s correctness.

Statement on the Use of Generative AI

Loading 2609.06512v1…