License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.32
URN: urn:nbn:de:0030-drops-171544
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17154/
Apers, Simon ;
Gawrychowski, Paweł ;
Lee, Troy
Finding the KT Partition of a Weighted Graph in Near-Linear Time
Abstract
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near-linear 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 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. In this work 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 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 near-minimum 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 2-respecting cut of T is a non-trivial near-minimum 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 Near-Linear Time}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {32:1--32:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17154},
URN = {urn:nbn:de:0030-drops-171544},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.32},
annote = {Keywords: Graph theory}
}
Keywords: |
|
Graph theory |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
15.09.2022 |