{"ID":2853086,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16741","arxiv_id":"2510.16741","title":"All-Pairs Minimum Cut using $\\tilde{O}(n^{7/4})$ Cut Queries","abstract":"We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph $G=(V,E)$ with $n$ vertices, our randomized algorithm constructs a Gomory-Hu tree of $G$, and thus solves the all-pairs minimum cut problem, using $\\tilde{O}(n^{7/4})$ cut queries.","short_abstract":"We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph $G=(V,E)$ with $n$ vertices, our randomized algorithm constructs a Gomory-Hu tree of $G$, and thus solves the all-pairs minimum cut problem, using $\\tilde{O}(n^{7/4})$ c...","url_abs":"https://arxiv.org/abs/2510.16741","url_pdf":"https://arxiv.org/pdf/2510.16741v1","authors":"[\"Yotam Kenneth-Mordoch\",\"Robert Krauthgamer\"]","published":"2025-10-19T07:52:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}