Source-linked AI summary
An ETH-based quasipolynomial lower bound for Dualization
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
TL;DR
Whether minimal transversals can be enumerated in output-polynomial time remains open. This paper reduces 3CNF satisfiability to comparing a constructed hypergraph family with the minimal transversals of another; under ETH, it rules out polynomial-time Dual and output-polynomial-time Dualization.
Problem
Whether Dualization admits output-polynomial-time enumeration remains open, and Dual captures its central completeness question.
Source: §1 · p. 2Method
A deterministic reduction constructs hypergraphs H and L from a 3CNF formula, with L⊆Tr(H) and satisfiability equivalent to L≠Tr(H).
Source: §1 · p. 3Results
Under ETH, Dual has no polynomial-time algorithm, and Dualization has no output-polynomial-time enumeration algorithm.
Source: §1 · p. 3Takeaways & Limitations
The paper transfers this obstruction to the related enumeration problems discussed in its introduction.
Source: §1 · p. 3
Abstract
from arXiv · showhide
Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from \textsc{3SAT} to the complement of \textsc{Dual}: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $\mathcal H$ and $\mathcal L$ of total size $2^{\bigoh(n^{2/3}(\log n)^{1/3})}$ such that $\mathcal L \subseteq \Tr(\mathcal H)$ and the formula is satisfiable if and only if $\mathcal L\neq \Tr(\mathcal H)$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither \textsc{Dual} nor \textsc{Dualization} admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for \textsc{Dual} and the combined input and output size for \textsc{Dualization}. In particular, \textsc{Dualization} cannot be solved in output-polynomial time under ETH.
1 Introduction
Dualization asks for all minimal transversals, while Dual tests whether a supplied family is complete; the general polynomial-time status remains open. This paper gives a deterministic subexponential reduction from 3SAT and derives ETH-based lower bounds for both problems.
1 Introduction
- Dualization is output-sensitive because a hypergraph can have exponentially more minimal transversals than its input size, and polynomial-time Dual is equivalent to output-polynomial enumeration.Thus Dual captures the central completeness question for transversal enumeration.Source: §1 · p. 2
- The general complexity remains unsettled despite Fredman and Khachiyan’s quasipolynomial-time algorithm, the best-known general upper bound described here.Numerous tractable cases are known under structural restrictions on hypergraphs and graphs.Source: §1 · p. 2
- Dualization’s hardness has been connected to enumeration problems in graphs and other domains, including minimal Steiner structures and minimal dominating sets.These connections support conditional lower bounds for related enumeration tasks.Source: §1 · p. 3
- A deterministic algorithm takes a 3CNF formula φ with n variables and constructs hypergraphs H and L with L ⊆ Tr(H); both have size bounded by 2^O(n^(2/3)(log n)^(1/3)) and are constructed in time 2^O(n^(2/3)(log n)^(1/3)).Source: §1 · p. 3
- Under ETH, Dual has no polynomial-time algorithm, and Dualization has no output-polynomial-time enumeration algorithm.The paper also transfers this obstruction to the related enumeration problems discussed in the introduction.Source: §1 · p. 3
2 Proof of Theorem 1
The proof encodes satisfying assignments as full-selector transversals, then pads hyperedges to control other minimal transversals; parameter choices keep the reduction subexponential. It derives ETH-based lower bounds for Dual and Dualization.
2.1 Constructing a hypergraph from a 3CNF formula
- A satisfying assignment corresponds to a valid full selector, and each valid full selector is a minimal transversal of the padded hypergraph.The construction uses vertices for partial assignments to variable blocks and clause edges hit when a represented partial assignment satisfies a clause.Source: §2.1 · pp. 3–4, §2.2 · p. 5
2.2 Padding hyperedges
- Polynomial evaluations label vertices so that two vertices from one block agree in at most t − 1 coordinates, allowing padding edges to be hit by a small subset.When two labels differ at a coordinate, that pair hits every edge in the corresponding padded family.Source: §2.2 · pp. 4–5
- The padding makes the existence of a minimal transversal larger than 2t equivalent to satisfiability, while any transversal containing two vertices from one block contains a transversal of size at most 2t.Thus large minimal transversals must be full selectors, which encode satisfying assignments.Source: §2.2 · p. 6
2.3 Setting parameters
- The construction has hypergraph size 2^{O(n^{2/3}(log n)^{1/3})}.The stated construction-time expression is also bounded by 2^{O(n^{2/3}(log n)^{1/3})}.Source: §2.3 · p. 7
2.4 Consequences of Theorem 1
- Under ETH, Dual has no polynomial-time algorithm and Dualization has no output-polynomial-time algorithm.The reduction also rules out running times of N^{o(√(log N/log log N))} for both problems.Source: §2.4 · pp. 7–8
- Theorem 1's lower bound transfers to minimal dominating set enumeration on co-bipartite graphs and to other enumeration problems reducible from Dualization in output-polynomial time.The listed transfers include minimal connected dominating sets on split graphs and several vertex-cover, Steiner, and related enumeration problems.Source: §2.4 · p. 8
3 Discussion
The paper rules out (output-)polynomial-time algorithms for Dual and Dualization under ETH and transfers this obstruction to related enumeration problems. It leaves open whether weaker assumptions suffice and where tractability boundaries lie.
3 Discussion
- The results rule out (output-)polynomial-time algorithms for Dual and Dualization under ETH and transfer the obstruction to many related enumeration problems.The discussion leaves questions about the necessary complexity assumption, tractable graph classes, and relationships among dualization-hard problems.Source: §3 · p. 8
- P≠NP alone is not shown to yield the qualitative lower bound; coNP-hardness of Dual would imply NP ⊆ QP, a consequence not excluded by P≠NP alone.The authors state that their reduction is insufficient for the weaker-assumption implication; this consequence would contradict ETH.Source: §3 · p. 9
- Minimal dominating sets have polynomial-delay enumeration on chordal graphs and output-polynomial enumeration on K_t-free graphs for fixed t, including bipartite graphs [5].Output-polynomial enumeration remains open for comparability graphs, graphs with no induced C4, and graphs with no induced 2K3 [6].Source: §3 · p. 9
- Bounded-dimension comparability algorithms and 2K2-free results suggest extensions, while the bounded-VC-dimension approach does not appear to settle the three open graph classes [6, 5, 28].These comparisons identify possible directions for extending existing algorithms.Source: §3 · p. 9
- Co-bipartite graphs capture the full difficulty of general Dualization [19], so ETH rules out output-polynomial enumeration in every graph class containing them, including perfect graphs.Source: §3 · p. 9
- For bipartite graphs, output-polynomial enumeration is known, but polynomial delay remains open; polynomial delay has been obtained for chordal bipartite graphs [8].Source: §3 · p. 9
- Further equivalences require a converse reduction to Dualization that preserves output-polynomial time and controls both transformed-instance and output size.Such equivalences are known for minimal dominating sets [19], minimal resolving sets in general graphs, and minimal geodetic sets in split graphs [2].Source: §3 · p. 9
4 AI disclosure
GPT-6 Astra originally discovered the proof of Theorem 1, and the authors reconstructed and revised the argument and used the model to prepare drafts of several manuscript parts. The authors verified the results and take responsibility for the mathematical claims and final manuscript.
4 AI disclosure
- GPT-6 Astra originally discovered the proof of Theorem 1; the authors subsequently reconstructed and revised the argument and rewrote its exposition.Source: §4 · p. 9
- The model also helped prepare drafts of several manuscript parts, while the authors verified the results and take responsibility for all mathematical claims and the final manuscript.Source: §4 · pp. 9–10