Faster Algorithms to Enumerate Hypergraph Transversals

DOI10.1007/978-3-662-49529-2_23MaRDI QIDQ2802949zbMATH OpenOpenAlexFDO

Authors Manfred Cochefert, Jean-François Couturier, Serge Gaspers, Dieter Kratsch

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: A transversal of a hypergraph is a set of vertices intersecting each hyperedge. We design and analyze new exponential-time algorithms to enumerate all inclusion-minimal transversals of a hypergraph. For each fixed k>2, our algorithms for hypergraphs of rank k, where the rank is the maximum size of a hyperedge, outperform the previous best. This also implies improved upper bounds on the maximum number of minimal transversals in n-vertex hypergraphs of rank k>2. Our main algorithm is a branching algorithm whose running time is analyzed with Measure and Conquer. It enumerates all minimal transversals of hypergraphs of rank 3 on n vertices in time O(1.6755^n). Our algorithm for hypergraphs of rank 4 is based on iterative compression. Our enumeration algorithms improve upon the best known algorithms for counting minimum transversals in hypergraphs of rank k for k>2 and for computing a minimum transversal in hypergraphs of rank k for k>5.

Recommendations

• An Efficient Algorithm for the Transversal Hypergraph Generation
• Computing and Combinatorics
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• Fast enumeration algorithms for non-crossing geometric graphs
• Fast enumeration algorithms for non-crossing geometric graphs
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• Algorithms for finding clique-transversals of graphs
• Total transversals in hypergraphs and their applications
• scientific article; zbMATH DE number 7666858
• scientific article; zbMATH DE number 1555984

Cited in

(11)

• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Computing and Combinatorics
• A global parallel algorithm for the hypergraph transversal problem
• An average study of hypergraphs and their minimal transversals
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Fast enumeration algorithms for non-crossing geometric graphs
• Enumerating minimal transversals of hypergraphs without small holes
• An incremental algorithm for computing the transversal hypergraph
• Counting minimal dominating sets

This page was built for publication: Faster Algorithms to Enumerate Hypergraph Transversals

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