Apers, Simon ;
Gawrychowski, Paweł ;
Lee, Troy
Finding the KT Partition of a Weighted Graph in NearLinear Time
Abstract
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a nearlinear time deterministic algorithm to compute the weight of a minimum cut in a simple graph G = (V,E). A key component of this algorithm is finding the (1+ε)KT partition of G, the coarsest partition {P_1, …, P_k} of V such that for every nontrivial (1+ε)near minimum cut with sides {S, ̄{S}} it holds that P_i is contained in either S or ̄{S}, for i = 1, …, k. In this work we give a nearlinear 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 treerespecting cuts (J. ACM'00).
We describe a number of applications of the algorithm. (i) The algorithm makes progress towards a more efficient algorithm for constructing the polygon representation of the set of nearminimum cuts in a graph. This is a generalization of the cactus representation, and was 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 Õ(n^{3/2}) to Õ(√{mn}), when the graph has n vertices and m edges. (iii) We describe a new type of randomized algorithm for minimum cut in simple graphs with complexity 𝒪(m + n log⁶ n). For graphs that are not too sparse, this matches the complexity of the current best 𝒪(m + n log² 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 of G, 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 2respecting cut of T is a nontrivial nearminimum cut of G. We give a 𝒪(m log⁴ n) time deterministic algorithm to compute a spanning forest of H.
BibTeX  Entry
@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2022.32,
author = {Apers, Simon and Gawrychowski, Pawe{\l} and Lee, Troy},
title = {{Finding the KT Partition of a Weighted Graph in NearLinear Time}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {32:132:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17154},
URN = {urn:nbn:de:0030drops171544},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.32},
annote = {Keywords: Graph theory}
}
15.09.2022
Keywords: 

Graph theory 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Issue date: 

2022 
Date of publication: 

15.09.2022 