The computation of all minimal transversals of a given hypergraph in output-polynomial time is a long standing open question known as TRANSVERSAL HYPERGRAPH GENERATION. One of the first attempts at this problem-the sequential method [Claude Berge, Hypergraphs, in: North-Holland Mathematical Library, vol. 45, North-Holland, 1989]-is not output-polynomial as was shown by Takata [Ken Takata, A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph, SIAM journal on Discrete Mathematics 21 (4) (2007) 936-946]. Recently, three new algorithms improving the sequential method were published and experimentally shown to perform very well in practice [James Bailey, Thomas Manoukian, Kotagiri Ramamohanarao, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, in: Proceedings of the 3rd IEEE International Conference on Data Mining, ICDM 2003, 19-22 December 2003, Melbourne, FL, USA, IEEE Computer Society, 2003, pp. 485-488; Guozhu Dong, Jinyan Li, Mining border descriptions of emerging patterns from dataset pairs, Knowledge and Information Systems 8 (2) (2005) 178-202; Dimitris J. Kavvadias, Elias C. Stavropoulos, An efficient algorithm for the transversal hypergraph generation, journal of Graph Algorithms and Applications 9 (2) (2005) 239-264]. Nevertheless, a theoretical worst-case analysis has been pending. We close this gap by proving lower bounds for all three algorithms. Thereby, we show that none of them are output-polynomial.
展开▼
机译：给定超图在输出多项式时间内的所有最小横截面的计算是一个长期存在的未解决问题，称为“横向超图生成”。解决此问题的首次尝试之一是顺序方法[Claude Berge，Hypergraphs，在：North-Holland Mathematical Library，vol。 45，North-Holland，1989]-不是输出式多项式，正如Takata [Ken Takata，对连续方法列出最图的最小命中集的最坏情况分析，SIAM离散数学21（4） （2007）936-946]。最近，发布了三种改进顺序方法的新算法，并通过实验证明它们在实践中表现良好[James Bailey，Thomas Manoukian，Kotagiri Ramamohanarao，一种用于计算超图横断的快速算法及其在挖掘新兴模式中的应用，摘录于：第三届IEEE数据挖掘国际会议，ICDM 2003，2003年12月19-22日，美国佛罗里达州墨尔本，IEEE计算机协会，2003年，第485-488页;董国柱，李金艳，从数据集对中挖掘新兴模式的边界描述，知识与信息系统8（2）（2005）178-202; Dimitris J. Kavvadias，Elias C. Stavropoulos，一种用于横向超图生成的有效算法，《图形算法与应用学报》 9（2）（2005）239-264]。尽管如此，理论上最坏情况的分析仍在进行中。我们通过证明所有三种算法的下界来弥合这一差距。因此，我们表明它们都不是输出多项式。
展开▼
