Achieving new upper bounds for the hypergraph duality problem through logic

DOI10.1137/15M1027267MaRDI QIDQ4637759zbMATH OpenWikidataFDO

Authors Georg Gottlob, Enrico Malizia

Publication date 26 April 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.2912

zbMATH Keywords

algorithmscomplexityDNF dualityfirst-order logicfirst-order logic with counting quantifiersgraph theoryhypergraph dualityhypergraph transversalshypergraphslimited nondeterminismlogical analysis of algorithms

Mathematics Subject Classification ID

Logic in computer science (03B70) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $mathcalG$ and $mathcalH$, decide whether $mathcalH$ consists precisely of all minimal transversals of $mathcalG$ (in which case we say that $mathcalG$ is the dual of $mathcalH$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $mathrmGC(lo{g}^{2}n,mathrmPTIME)$, where $mathrmGC(f(n),mathcalC)$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $mathcalC$. It was conjectured that non-DUAL is in $mathrmGC(lo{g}^{2}n,mathrmLOGSPACE)$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $mathrmGC(lo{g}^{2}n,mathrm{TC}^0)$ which is a subclass of $mathrmGC(lo{g}^{2}n,mathrmLOGSPACE)$. We here refer to the logtime-uniform version of $mathrm{TC}^0$, which corresponds to $mathrmFO(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 non-DUAL that requires to guess $O(lo{g}^{2}n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $mathrmFO(COUNT)$. From this result, by the well known inclusion $mathrm{TC}^{0}subseteqmathrmLOGSPACE$, it follows that DUAL belongs also to $mathrmDSPACE[lo{g}^{2}n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $mathcalG$ and $mathcalH$, computes in quadratic logspace a transversal of $mathcalG$ missing in $mathcalH$.

Recommendations

• Achieving new upper bounds for the hypergraph duality problem through logic
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Resolution based algorithms for the transversal hypergraph generation problem
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems

Cites work

• A correction to the algorithm in Reiter's theory of diagnosis
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• A global parallel algorithm for the hypergraph transversal problem
• A theory of diagnosis from first principles
• Achieving new upper bounds for the hypergraph duality problem through logic
• Advances in Artificial Intelligence
• Algorithms for inferring functional dependencies from relations
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Complexity of identification and dualization of positive Boolean functions
• Computational aspects of monotone dualization: a brief survey
• Computer Science Logic
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Elements of finite model theory.
• How to assign votes in a distributed system
• scientific article; zbMATH DE number 4201601 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1354130 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 1149451 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• scientific article; zbMATH DE number 4115979 (Why is no real title available?)
• scientific article; zbMATH DE number 2086380 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Logical foundations of proof complexity
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On maximal frequent and minimal infrequent sets in binary matrices
• On the Amount of Nondeterminism and the Power of Verifying
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of inferring functional dependencies
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• On the universal and existential fragments of the \(\mu\)-calculus
• On uniformity within \(NC^ 1\)
• Parametrized complexity theory.

Cited in

(6)

• Query answering over inconsistent knowledge bases: a probabilistic approach
• Preference-based inconsistency-tolerant query answering under existential rules
• Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
• Achieving new upper bounds for the hypergraph duality problem through logic
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On a logical approach to estimating computational complexity of potentially intractable problems.

This page was built for publication: Achieving new upper bounds for the hypergraph duality problem through logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637759)