Minimal-to-Maximal Conversion Search Is Not Output-Polynomial
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem called the Transversal Hypergraph problem, which involves listing all the smallest hitting sets of a given hypergraph. They focus on an existing algorithm called MMCS, known to work well in practice but without guarantees on its worst-case speed. They prove that MMCS cannot always run in time proportional to the output size, meaning it is not output-polynomial. The authors analyze how different heuristic choices affect the algorithm's performance and introduce a new heuristic that improves its practical speed based on their experiments.
Transversal Hypergraph ProblemMinimal Hitting SetsOutput-Polynomial AlgorithmMMCS AlgorithmHeuristicsAlgorithm AnalysisHypergraphEnumeration AlgorithmsRunning TimeWorst-Case Complexity
Authors
Bennet Hörmann, Martin Schirneck
Abstract
The Transversal Hypergraph problem is to enumerate (list) all inclusion-wise minimal hitting sets of a given hypergraph $\mathcal{H}$. It is the most important open question in enumeration whether this problem admits an output-polynomial algorithm whose running time scales polynomially with the size of $\mathcal{H}$ and the number of solutions. Currently, Minimal-to-Maximal Conversion Search (MMCS) by Murakami and Uno [DAM 2014] is the most efficient algorithm for real-world instances, but there are no worst-case performance guarantees known for it. We prove that MMCS is in fact not output-polynomial. The lower bound construction motivates a more detailed analysis of how certain heuristic choices in the algorithm design affect the running time. We conduct a thorough analysis of those heuristics and, based on this, propose new extension. We then show in extensive running time experiments that this new heuristic further improves practical performance.