Minimal-to-Maximal Conversion Search Is Not Output-Polynomial

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.