Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
Georg Gottlob, Enrico Malizia · SIAM Journal on Computing · 2018
The hypergraph duality problem Dual is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$ or, equivalently, the transversal hypergraph of $\mathcal{H}$). This problem is equivalent to deciding whether two given nonredundant monotone disjunctive normal forms/conjunctive normal forms are dual. It is known that $\overline{{\sc Dual}}$, the complementary problem to Dual, is in GC($\log^2 n$, PTIME), where GC($f(n)$, $\mathcal{C}$) denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $\mathcal{C}$. It was conjectured that $\overline{{\sc Dual}}$ is in GC($\log^2 n$, LOGSPACE). In this paper we prove this conjecture and actually place the $\overline{{\sc Dual}}$ problem into the complexity class GC($\log^2 n$, TC$^{0}$) which is a subclass of GC($\log^2 n$, LOGSPACE). We here refer to the logtime-uniform version of TC$^{0}$, which corresponds to FO(COUNT), i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for $\overline{{\sc Dual}}$ that requires one to guess $O(\log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in FO(COUNT). From this result, by the well-known inclusion ${TC$^0$}\subseteq{LOGSPACE}$, it follows that Dual also belongs to ${DSPACE}[\log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $\mathcal{G}$ and $\mathcal{H}$, computes in quadratic logspace a transversal of $\mathcal{G}$ missing in $\mathcal{H}$.