arXiv preprint ·
An ETH-based quasipolynomial lower bound for Dualization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $H$ and $L$ of total size $2^{O(n^{2/3}(\log n)^{1/3})}$ such that $L \subseteq Tr(H)$ and the formula is satisfiable if and only if $L\neq Tr(H)$, where $Tr(H)$ is the set of minimal transversals of $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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Polynomial directed treewidth forces a large bramble with congestion two
Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
A Fast Greedy Algorithm with a 0.45 Approximation Guarantee for the Airplane Refueling Problem
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.