Faster Algorithms to Enumerate Hypergraph Transversals
2016
A transversal of a hypergraph is a set of vertices intersecting each hyperedge. We design and analyze new exponential-time polynomial-space algorithms to enumerate all inclusion-minimal transversals of a hypergraph. For each fixed \(k\ge 3\), 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\ge 3\). 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 in time \(O(1.6755^n)\). Our enumeration algorithms improve upon the best known algorithms for counting minimum transversals in hypergraphs of rank k for \(k\ge 3\) and for computing a minimum transversal in hypergraphs of rank k for \(k\ge 6\).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
22
References
4
Citations
NaN
KQI