PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Multilayered PCPs and Hypergraph Vertex Cover

Karthik C. S., Dor Minzer

arXiv:2609.06775v1cs.CCcs.DS

TL;DR

Improved multilayered PCP constructions are sought as tools for progress on NP-hardness of hypergraph vertex cover. This work presents constructions with 2-to-2 constraints and quasi-linear size, alongside a limitation on improving related time-hardness results with current techniques.

  • Problem

    Multilayered PCPs are an important ingredient in PCP constructions, and the work seeks stronger constructions to advance hypergraph vertex-cover NP-hardness.

    Source: §1 · p. 1

  • Method

    The paper views collision games as multilayered PCPs and presents constructions targeting 2-to-2 constraints and quasi-linear size.

    Source: §1.2 · pp. 2–3, §1.4.1 · p. 5

  • Results

    One construction gives a quasi-linear-size layered instance from 3-SAT, while another yields NP-hardness for distinguishing weakly dense layered label-cover instances with 2-to-2 constraints.

    Source: §1.2 · pp. 2–3

  • Takeaways & Limitations

    The constructions provide new multilayered PCP tools for applications, particularly hypergraph vertex cover.

    Source: §1 · p. 1

    Current techniques for improving the sub-exponential-time hardness factor rely on d-to-1 games, whose reductions incur polynomial blow-up.

    Source: §1.2.1 · p. 3

Abstract

from arXiv · show

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and another one with $2$-to-$2$ constraints. Using these constructions we obtain the following results for the hypergraph vertex cover problem: $\bullet$ For $k=3$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $3$-uniform hypergraph within factor $1+\sqrt{2}-\varepsilon$ is NP-hard. Previously, the best known result due to [Dinur, Guruswami, Khot, Regev, SICOMP 2005] achieved a factor of $2-\varepsilon$. $\bullet$ For $k\geq 4$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $k$-uniform hypergraph within factor $k-\varepsilon$ is NP-hard, which is tight. Previous works established this result assuming the Unique-Games Conjecture [Khot, Regev, JCSS 2008], and a weaker factor of $k-1-\varepsilon$ for standard NP-hardness [Dinur, Guruswami, Khot, Regev, SICOMP 2005]. $\bullet$ Assuming the Exponential Time Hypothesis, for all $k\geq 3$ and $\varepsilon>0$ there is $C>0$ such that no $2^{n/\log^C n}$-time algorithm approximates the minimum vertex cover in a $k$-uniform, $n$-vertex hypergraph within factor $k-1-\varepsilon$. The proofs were obtained using ChatGPT 5.6 Pro and subsequently rewritten by the communicators.

1 Introduction

The introduction presents two improved multilayered PCP constructions and applies them to strengthen hypergraph vertex-cover hardness and derive further hardness results. It also describes coupling improvements using slack for k=3 and omission tradeoffs for k≥4 when a,b≥2.

1.1 Label Cover

  • The paper defines multilayered label cover through pairwise label-cover instances across layers, and notes that strong density implies weak density with slightly worse parameters.The authors include strong density as a potentially useful notion, although known applications use weak density.Source: §1.1 · p. 2

1.2 Main Results

  • For all λ ∈ (0, 1], ε > 0, and ℓ ∈ N, it is NP-hard to distinguish ℓ-layered, (1/2, λ)-weakly dense label cover instances whose pairwise games are 2-to-2 with a common alphabet of size at most C.In the yes case, partial labelings on subsets of fractional size at least 1 − ε satisfy all constraints on edges between those subsets.Source: §1.2 · pp. 2–3
  • A polynomial-time reduction produces a strongly dense projection multilayered PCP of size n log^C n and constant alphabet, with perfect completeness and soundness at most ε.Theorem 1.5 gives this construction from a 3-SAT formula, with parameters λ, ε, and the number of layers ℓ.Source: §1.2 · p. 3

1.2.1 Implications for Hypergraph Vertex Cover

  • For every integer k ≥ 4 and ε > 0, given a k-uniform weighted hypergraph H, it is NP-hard to approximate the minimum weight of a vertex cover in H within factor k −ε.Source: §1.2.1 · p. 3
  • Assuming ETH, no 2^(n/log^C n)-time algorithm approximates minimum vertex cover in a k-uniform n-vertex hypergraph within k−1−ε, for any k ≥ 3 and ε > 0.The proof uses the multilayered PCP of Theorem 1.5 in the construction from [DGKR05, Section 5].Source: §1.2.1 · p. 3

1.3 Other Implications

  • The results also yield hardness for simple hypergraph vertex cover, feedback vertex sets for bounded cycles, and H-transversal in fixed 2-connected graphs.For simple hypergraphs, the stated factors are 1+sqrt(2)−ε for 3-uniform instances and k−ε for k ≥ 4, assuming NP ⊄ BPP; for H-transversal the factor is k−ε under the same assumption.Source: §1.3 · p. 4

1.4.1 Multilayered PCPs

  • The PCP constructions use collision games as multilayered PCPs; the quasi-linear construction additionally addresses density and projection constraints.The density issue is handled by a reduction using bipartite expanders, while enlarging alphabets turns the collision game into a projection game.Source: §1.4.1 · p. 5

1.4.2 Hypergraph Vertex Cover

  • For vertex-cover reductions, p-biased long codes encode labels as dictatorships, and the key improvement is robust hyperedge couplings for 2-to-2 constraints at p > 1−1/(k−1).The couplings are designed so that satisfying label pairs avoid hyperedges, nonsatisfying pairs are detected, and both properties persist for nearby families.Source: §1.4.2 · pp. 5–6
  • For k=3, slack permits a coupling with p > 1 − 1/(k−1), improving on.The passage attributes the improvement to overshooting the probability of B_s ∩ Q_i = Q_i while correctly matching the probability that B_s ∩ Q_i = ∅.Source: §1.4.2 · p. 7
  • When a,b are both at least 2, trading off omissions among A’s and B’s enables couplings that reach the full target p for k≥4.The passage says this tradeoff is possible only for k≥4.Source: §1.4.2 · p. 7

2 Preliminaries

The preliminaries establish the label-cover starting points and biased-long-code tools used in the paper. They include a bounded-parameter hardness theorem, a quasi-linear 3-SAT reduction, and influence/junta machinery.

2.1 PCPs

  • The paper uses 2-to-1 games with imperfect completeness, whose weighted instances can be converted to unweighted, biregular instances using standard techniques.The stated completeness differs from that in the cited papers, but their construction achieves it.Source: §2.1 · p. 7
  • Theorem 2.1 makes it NP-hard to distinguish a 2-to-1 game with near-complete partial assignments on the left from one where no labeling satisfies more than an ε fraction of constraints.In the yes case, a partial labeling on at least a 1−ε fraction of left vertices satisfies all constraints between those vertices and the right side.Source: §2.1 · p. 7
  • Theorem 2.2 reduces a 3-SAT formula of size n to a biregular projection label-cover instance of size at most n log^C n, with alphabet size and degree at most C.Source: §2.1 · p. 8

2.2 Biased Long-code

  • The p-biased Kneser graph has subsets of Σ as vertices, disjoint pairs as edges, and vertex weights μp(A)=p^|A|(1−p)^|Σ\A|.Source: §2.2 · p. 8
  • For a family with total influence at most K, Lemma 2.8 gives an ε-close J-junta with J of size 2^{O_{p,ε}(K)}; junta membership depends only on projection onto J.Source: §2.2 · p. 8

3 The Multilayered PCPs

The paper constructs multilayered PCPs by arranging collision games between copies of a label-cover instance. A quasi-linear, expanding construction additionally lifts local labels to recover projection constraints.

3.1 Proof of Theorem 1.4

  • Theorem 1.4’s construction takes ℓ copies of the left side and places a collision game between each pair, with constraints requiring projections of labels to agree at a shared right vertex.Each cross-layer edge is formed by sampling a right vertex and two of its left neighbors.Source: §3.1 · p. 9
  • The soundness argument for the collision construction converts satisfied cross-layer constraints into expected satisfaction in the original label-cover instance under induced labelings.Source: §3.1 · p. 9

3.2 A Quasi-linear, Expanding Multilayered PCP: Proof of Theorem 1.5

  • Theorem 3.1 reduces 3-SAT of size n to a biregular projection label-cover instance of size at most n log^C n, with bounded alphabet and degree and second singular value at most λ.Source: §3.2 · p. 10
  • The quasi-linear construction builds a multilayered collision game from the base instance, then enlarges layer alphabets with locally valid neighborhood labelings to restore projection constraints.The lifted labels encode assignments within a specified neighborhood radius, and edges require agreement on the smaller neighborhood.Source: §3.2 · pp. 10–11
  • The multilayered construction inherits expansion from the base instance, and its soundness satisfies val(Ψ′) ≤ val(Ψ).The expansion argument uses the product of the base and auxiliary graph adjacency operators.Source: §3.2 · pp. 10–11

4 The Hypergraph Vertex Cover Result

The section proves the hypergraph vertex-cover result by analyzing a reduction in the language of independent sets; the complement of an independent set gives a vertex cover. Its soundness analysis uses balanced long-code couplings to bound independent-set weight.

4 The Hypergraph Vertex Cover Result

  • The construction splits hyperedge vertices more evenly between two long codes, making the required coupling easier to construct.The section gives distinct coupling constructions for k≥4 and k=3.Source: §4 · p. 12

4.1 The Construction for Theorem 4.1

  • For each multilayer PCP edge, H includes a hyperedge when the two selected-set intersections contain no label pair satisfying that edge's constraint.The construction replaces each layered vertex with copies indexed by subsets of the alphabet and assigns them p-biased weights.Source: §4.1 · p. 12

4.2 Completeness Analysis

  • If Ψ is in the Yes case of Theorem 1.4, H contains an independent set of weight at least p(1−ε).The proof builds the set from partial labelings that satisfy the constraints between layers.Source: §4.2 · p. 12

4.3 Tools for the Soundness Analysis

  • For a 2-to-2 constraint, the coupling preserves p-biased marginals while ensuring the relevant intersections contain no satisfying label pair.The section states this property for two sets on one side and k−2 sets on the other.Source: §4.3 · p. 13

4.4 Soundness Analysis

  • For p=pc−η, if Ψ is (1/2, λ)-weakly dense and every layer-pair value is at most ε, H's largest independent set has weight at most η.The bound holds for sufficiently large ℓ and sufficiently small λ and ε.Source: §4.4 · p. 14
  • For adjacent great vertices, the extended juntas contain a satisfying label pair; otherwise the soundness proof constructs a hyperedge contradicting independence.The contradiction uses sets with probability at least 1−2kη > 0.Source: §4.4 · pp. 15–16
Loading 2609.06775v1…