Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
SIAM Journal on Computing
Society for Industrial and Applied Mathematics
© 2018 Society for Industrial and Applied Mathematics.
The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs G and H, decide whether H consists precisely of all minimal transversals of G (in which case we say that G is the dual of H, or, equivalently, the transversal hypergraph of H). This problem is equivalent to deciding whether two given non-redundant monotone DNFs/CNFs are dual. It is known that co-DUAL, the complementary problem to DUAL, is in GC(log^2 n, PTIME), where GC(f(n), 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 C. It was conjectured that co-DUAL is in GC(log^2 n, LOGSPACE). In this paper we prove this conjecture and actually place the co-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 co-DUAL that requires 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 belongs also 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 G and H, computes in quadratic logspace a transversal of G missing in H.
G. Gottlob’s work was supported by the EPSRC Programme Grant EP/M025268/ “VADA: Value Added Data Systems – Principles and Architecture”. E. Malizia’s work was mainly supported by the European Commission through the European Social Fund and by the Region of Calabria (Italy). Malizia received additional funding from the ERC grant 246858 (DIADEM) and the above mentioned EPSRC grant “VADA”
This is the author accepted manuscript. The final version is available from SIAM via the DOI in this record.
Vol. 47 (2), pp. 456-492.