{"ID":5935763,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T02:10:06.972658124Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03266","arxiv_id":"2607.03266","title":"An FPT Algorithm for Diverse Minimum s-t Cuts","abstract":"We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum s-t cuts C_1, ..., C_k such that for any i,j in [k], the number of edges in the symmetric difference of C_i and C_j is at least d. For d being 1 or 2, the problem corresponds to counting minimum s-t cuts in G, which is #P-complete [Provan and Ball, SICOMP 1983]. The problem is also known to be NP-complete already for k = 3 [de Berg, López Martínez, Spieksma, ISAAC 2024]. Our main result shows that the problem is fixed-parameter tractable (FPT) when parameterized by the combined parameter k + d. The main ingredients of our FPT algorithm build on novel structural properties of diverse minimum s-t cuts and a non-trivial application of the flow-augmentation technique of Kim, Kratsch, Pilipczuk, and Wahlström [JACM 2025].","short_abstract":"We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum s-t cuts C_1, ..., C_k such that for any i,j in [k], the number of edges in the symmetric difference of C_i and C_j is at least d. For d be...","url_abs":"https://arxiv.org/abs/2607.03266","url_pdf":"https://arxiv.org/pdf/2607.03266v1","authors":"[\"Krishnan Dehaleesan\",\"Pål Grønås Drange\",\"Fedor V. Fomin\",\"Petr A. Golovach\",\"Laure Morelle\"]","published":"2026-07-03T12:35:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}