Counting minimal transversals of -acyclic hypergraphs

DOI10.1016/J.JCSS.2018.10.002MaRDI QIDQ1713476zbMATH OpenOpenAlexFDO

Authors Benjamin Bergougnoux, Florent Capelli, Mamadou Moustapha Kanté

Publication date 25 January 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

\(\beta\)-acyclic hypergraphscounting problemdominating setsminimal transversalsstrongly chordal graphs

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Transversal (matching) theory (05D15)

Abstract: We prove that one can count in polynomial time the number of minimal transversals of $$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in [M.M. Kant'e and T. Uno, Counting Minimal Dominating Sets, TAMC'17].

Recommendations

• Counting minimal dominating sets
• Enumerating minimal transversals of hypergraphs without small holes
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Foundations of Information and Knowledge Systems
• On the number of minimal transversals in 3-uniform hypergraphs

Cites work

• Approximately counting locally-optimal structures
• Computational aspects of monotone dualization: a brief survey
• Counting minimal dominating sets
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the counting complexity of propositional circumscription
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• On the enumeration of minimal dominating sets and related notions
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Three Partition Refinement Algorithms
• Understanding model counting for -acyclic CNF-formulas
• Understanding the complexity of \#SAT using knowledge compilation

Cited in

(2)

• Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
• Bounding the Mim-Width of Hereditary Graph Classes.

This page was built for publication: Counting minimal transversals of \(\beta\)-acyclic hypergraphs

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