Show simple item record

dc.contributor.authorGottlob, G
dc.contributor.authorMalizia, E
dc.date.accessioned2017-11-28T11:01:34Z
dc.date.issued2018-04-12
dc.description.abstractThe 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.en_GB
dc.description.sponsorshipG. 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”en_GB
dc.identifier.citationVol. 47 (2), pp. 456-492.en_GB
dc.identifier.doi10.1137/15M1027267
dc.identifier.urihttp://hdl.handle.net/10871/30485
dc.language.isoenen_GB
dc.publisherSociety for Industrial and Applied Mathematicsen_GB
dc.relation.urlhttp://hdl.handle.net/10871/33327
dc.rights© 2018 Society for Industrial and Applied Mathematics.
dc.subjecthypergraphsen_GB
dc.subjecthypergraph transversalsen_GB
dc.subjecthypergraph dualityen_GB
dc.subjectDNF dualityen_GB
dc.subjectcomplexityen_GB
dc.subjectfirst order logicen_GB
dc.subjectlogical analysis of algorithmsen_GB
dc.subjectTC^0en_GB
dc.subjectfirst order logic with counting quantifiersen_GB
dc.subjectalgorithmsen_GB
dc.subjectlimited nondeterminismen_GB
dc.subjectgraph theoryen_GB
dc.titleAchieving New Upper Bounds for the Hypergraph Duality Problem through Logicen_GB
dc.typeArticleen_GB
dc.identifier.issn0097-5397
dc.descriptionThis is the author accepted manuscript. The final version is available from SIAM via the DOI in this record.en_GB
dc.descriptionThe final published version is also in ORE: http://hdl.handle.net/10871/33327
dc.identifier.journalSIAM Journal on Computingen_GB


Files in this item

This item appears in the following Collection(s)

Show simple item record