Finding the KT partition of a weighted graph in near-linear time
share
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near-linear time deterministic algorithm for minimum cut in a simple graph G = (V,E). A key component is finding the (1+ε)-KT partition of G, the coarsest partition {P_1, …, P_k} of V such that for every non-trivial (1+ε)-near minimum cut with sides {S, S̅} it holds that P_i is contained in either S or S̅, for i=1, …, k. Here we give a near-linear time randomized algorithm to find the (1+ε)-KT partition of a weighted graph. Our algorithm is quite different from that of Kawarabayashi and Thorup and builds on Karger's framework of tree-respecting cuts (J. ACM'00). We describe applications of the algorithm. (i) The algorithm makes progress towards a more efficient algorithm for constructing the polygon representation of the set of near-minimum cuts in a graph. This is a generalization of the cactus representation initially described by Benczúr (FOCS'95). (ii) We improve the time complexity of a recent quantum algorithm for minimum cut in a simple graph in the adjacency list model from O(n^3/2) to O(√(mn)). (iii) We describe a new type of randomized algorithm for minimum cut in simple graphs with complexity O(m + n log^6 n). For slightly dense graphs this matches the complexity of the current best O(m + n log^2 n) algorithm which uses a different approach based on random contractions. The key technical contribution of our work is the following. Given a weighted graph G with m edges and a spanning tree T, consider the graph H whose nodes are the edges of T, and where there is an edge between two nodes of H iff the corresponding 2-respecting cut of T is a non-trivial near-minimum cut of G. We give a O(m log^4 n) time deterministic algorithm to compute a spanning forest of H.
READ FULL TEXT