A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs

Sergio Caracciolo, Gregor Masbaum, Alan D. Sokal +1

Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4,…