A Hypergraph Container Method on Spread SAT: Approximation and Speedup
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918450657492992 |
|---|---|
| author | Han, Zicheng Lin, Yupeng Ma, Jie Zhang, Xiande |
| author_facet | Han, Zicheng Lin, Yupeng Ma, Jie Zhang, Xiande |
| contents | We develop a hypergraph container method for the Boolean Satisfiability Problem (SAT) via the newly developed container results [Campos and Samotij (2024)]. This provides an explicit connection between the extent of spread of clauses and the efficiency of container-based algorithms. Informally, the more evenly the clauses are distributed, the stronger the shrinking effect of the containers, which leads to faster algorithms for SAT.
To quantify the extent of spread, we use a weighted point of view, in which a clause of size $s$ receives weight $p^s$ for some $0<p\le 1$.In this way, we introduce the notion of $(λ,p)_k$-structure for SAT formulas, where $λ$ is the spread parameter and $k$ is the maximum size of clauses. By the almost-independence property of containers, we prove that for formulas with $(λ,p)_k$-structures, one can distinguish between ``unsatisfiable formulas'' and ``formulas satisfying at least a $(1-δ)$-fraction of clauses'' in sub-exponential time. This shows that sufficiently spread formulas are not worst-case instances for Gap-ETH. Moreover, we show that the speedup is directly controlled by the spread parameter $λ$, yielding faster exact algorithms for SAT formulas containing a $(λ,p)_k$-structure. This result extends previous work [Zamir (STOC 2023)] to the non-uniform case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15031 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Hypergraph Container Method on Spread SAT: Approximation and Speedup Han, Zicheng Lin, Yupeng Ma, Jie Zhang, Xiande Combinatorics Computational Complexity We develop a hypergraph container method for the Boolean Satisfiability Problem (SAT) via the newly developed container results [Campos and Samotij (2024)]. This provides an explicit connection between the extent of spread of clauses and the efficiency of container-based algorithms. Informally, the more evenly the clauses are distributed, the stronger the shrinking effect of the containers, which leads to faster algorithms for SAT. To quantify the extent of spread, we use a weighted point of view, in which a clause of size $s$ receives weight $p^s$ for some $0<p\le 1$.In this way, we introduce the notion of $(λ,p)_k$-structure for SAT formulas, where $λ$ is the spread parameter and $k$ is the maximum size of clauses. By the almost-independence property of containers, we prove that for formulas with $(λ,p)_k$-structures, one can distinguish between ``unsatisfiable formulas'' and ``formulas satisfying at least a $(1-δ)$-fraction of clauses'' in sub-exponential time. This shows that sufficiently spread formulas are not worst-case instances for Gap-ETH. Moreover, we show that the speedup is directly controlled by the spread parameter $λ$, yielding faster exact algorithms for SAT formulas containing a $(λ,p)_k$-structure. This result extends previous work [Zamir (STOC 2023)] to the non-uniform case. |
| title | A Hypergraph Container Method on Spread SAT: Approximation and Speedup |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2604.15031 |