The complexity of finding arborescences in hypergraphs (Q1205723): Difference between revisions

We prove that ASP is NP-complete even if all edges in \(H\) are of cardinality three. This is the strongest possible result, since the case where all edges are of cardinality two is solvable in polynomial time (this case can be represented as the intersection of two matroids, see [\textit{A. Frank}, J. Algorithms 2, 328-336 (1981; Zbl 0484.05025)]). The fastest known algorithm for this special case is due to \textit{R. E. Tarjan} [Networks 7, 25-35 (1977; Zbl 0379.90100)] and runs in \(O(\min\{m\log n,n^ 2\})\) time, where \(n\) denotes the number of vertices and \(m\) denotes the number of edges of the graph. Further we prove that the corresponding problem in undirected graphs is solvable in polynomial time by the standard Greedy algorithm, since the underlying structure forms a matroid.