Finding the KT Partition of a Weighted Graph in Near-Linear Time

Apers, S; Gawrychowski, P; Lee, T

Finding the KT Partition of a Weighted Graph in Near-Linear Time

Apers, S Gawrychowski, P Lee, T

Permalink

Publication Type:: Conference Proceeding
Citation:: 2022, 245, (-)
Issue Date:: 2022-09-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (686.1 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Apers, S
dc.contributor.author	Gawrychowski, P
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.date.accessioned	2023-05-25T03:58:20Z
dc.date.available	2023-05-25T03:58:20Z
dc.date.issued	2022-09-01
dc.identifier.citation	2022, 245, (-)
dc.identifier.issn	1868-8969
dc.identifier.uri	http://hdl.handle.net/10453/170462
dc.description.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 P1 Pk of V such that for every non trivial 1 near minimum cut with sides S S it holds that Pi 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 Oe n3 2 to Oe 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 O m nlog6 n For graphs that are not too sparse this matches the complexity of the current best O m nlog2 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 O mlog4 n time deterministic algorithm to compute a spanning forest of H Simon Apers Pawe Gawrychowski and Troy Lee
dc.language	en
dc.relation.isbasedon	10.4230/LIPIcs.APPROX/RANDOM.2022.32
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Finding the KT Partition of a Weighted Graph in Near-Linear Time
dc.type	Conference Proceeding
utslib.citation.volume	245
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access	*
dc.date.updated	2023-05-25T03:58:19Z
pubs.issue	-
pubs.volume	245
utslib.citation.issue	-

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 P1 Pk of V such that for every non trivial 1 near minimum cut with sides S S it holds that Pi 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 Oe n3 2 to Oe 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 O m nlog6 n For graphs that are not too sparse this matches the complexity of the current best O m nlog2 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 O mlog4 n time deterministic algorithm to compute a spanning forest of H Simon Apers Pawe Gawrychowski and Troy Lee

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/170462