Work-optimal parallel minimum cuts for non-sparse graphs

Andrés López-Martínez; Sagnik Mukhopadhyay; Danupon Nanongkai

doi:10.48550/arXiv.2102.06565

Work-optimal parallel minimum cuts for non-sparse graphs

Andrés López-Martínez
, Sagnik Mukhopadhyay
, Danupon Nanongkai

Computer Science

Research output: Working paper/Preprint › Preprint

Abstract

We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For m ≥ n^1+ϵ for any constant ϵ > 0, our algorithm requires O(mlogn) work and O(log³n) depth and succeeds with high probability. Its work matches the best O(mlogn) runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by O(log³n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.

Original language	English
Publisher	arXiv
DOIs	https://doi.org/10.48550/arXiv.2102.06565
Publication status	Published - 12 Feb 2021

Access to Document

10.48550/arXiv.2102.06565Licence: Creative Commons: Attribution (CC BY)

1 Conference contribution

Work-optimal parallel minimum cuts for non-sparse graphs
López-Martínez, A., Mukhopadhyay, S. & Nanongkai, D., 6 Jul 2021, SPAA 2021: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery , p. 351-361 11 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cite this

@techreport{d4fb37f3379a418fa16341926a09e4f7,

title = "Work-optimal parallel minimum cuts for non-sparse graphs",

abstract = "We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For m ≥ n1+ϵ for any constant ϵ > 0, our algorithm requires O(mlogn) work and O(log3n) depth and succeeds with high probability. Its work matches the best O(mlogn) runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by O(log3n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.",

author = "Andr{\'e}s L{\'o}pez-Mart{\'i}nez and Sagnik Mukhopadhyay and Danupon Nanongkai",

year = "2021",

month = feb,

day = "12",

doi = "10.48550/arXiv.2102.06565",

language = "English",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Work-optimal parallel minimum cuts for non-sparse graphs

AU - López-Martínez, Andrés

AU - Mukhopadhyay, Sagnik

AU - Nanongkai, Danupon

PY - 2021/2/12

Y1 - 2021/2/12

N2 - We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For m ≥ n1+ϵ for any constant ϵ > 0, our algorithm requires O(mlogn) work and O(log3n) depth and succeeds with high probability. Its work matches the best O(mlogn) runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by O(log3n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.

AB - We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For m ≥ n1+ϵ for any constant ϵ > 0, our algorithm requires O(mlogn) work and O(log3n) depth and succeeds with high probability. Its work matches the best O(mlogn) runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by O(log3n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.

UR - https://www.scopus.com/pages/publications/85102032221

U2 - 10.48550/arXiv.2102.06565

DO - 10.48550/arXiv.2102.06565

M3 - Preprint

BT - Work-optimal parallel minimum cuts for non-sparse graphs

PB - arXiv

ER -

Work-optimal parallel minimum cuts for non-sparse graphs

Abstract

Access to Document

Fingerprint

Research output

Work-optimal parallel minimum cuts for non-sparse graphs

Cite this