Packing hypertrees and the k-cut problem in Hypergraphs

Abstract

We give a combinatorial algorithm to find a maximum packing of hypertrees in a capacitated hypergraph. Based on this we extend to hypergraphs several algorithms for the $k$-cut problem, that are based on packing spanning trees in a graph. In particular we give a γ- approximation algorithm for hypergraphs of rank γ, extending the work of Ravi and Sinha for graphs. We also extend the work of Chekuri, Quanrud and Xu in graphs, to give an algorithm for the $k$-cut problem in hypergraphs that is polynomial if $k$ and the rank of the hypergraph are fixed. We also give a combinatorial algorithm to solve a linear programming relaxation of this problem in hypergraphs.