Fixed-Parameter Tractability of Hedge Cut

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut can be solved in quasipolynomial-time, raising the hope for a polynomial time algorithm. Jaffke, Lima, Masarík, Pilipczuk, and Souza [SODA 2023] complemented this result by showing that assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists. In this paper, we show that Hedge Cut is fixed-parameter tractable parameterized by the solution size ℓ by providing an algorithm with running time O(log n)+ℓ ℓ • m O(1) , which can be upper bounded by c ℓ • (n + m) O(1) for any constant c > 1. This running time captures at the same time the fact that the problem is quasipolynomial-time solvable, and that it is fixed-parameter tractable parameterized by ℓ. We further generalize this algorithm to an algorithm with running time O(k log n)+ℓ ℓ • n O(k) • m O(1) for Hedge k-Cut.