{Weighted Min-Cut is Easy
Andrés López-Martínez \thanks{KTH Royal Institute of technology
Sweden
anlm@kth.se
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon$ for any constant $\epsilon>0$ %\andres{for any fixed $\epsilon > \log \log n / \log n$, %$\epsilon = \Omega((\log \log n) / \log n)$ our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOC’20; GMW SOSA'21]. % This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. % We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m=\Omega(n\log^5 n$) and any constant $\epsilon>0$, our algorithm requires $O(m \log n + n^{1+\epsilon)$ work and $O(\log^3 n)$ depth and succeeds with high probability. % Its work matches the best $O(m \log n + n^{1+\epsilon)$ runtime for sequential algorithms [MN STOC’20; GMW SOSA'21]. % % % This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. %We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For any $\epsilon>0$, our algorithm requires $O(m(\log n)/\epsilon + n^{1+\epsilon + n\log^4 n)$ work and $O(\log^3 n)$ depth. % For non-sparse graphs ($m=\Omega(n\log^4 n$)), this matches the best $O(m(\log n)/\epsilon + n^{1+\epsilon + n\log^2 n)$ runtime for sequential algorithms by Mukhopadhyay and Nanongkai [STOC’20] and GMW [SOSA'21], % % % and improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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 of Mukhopadhyay and Nanongkai [STOC’20] and GMW [SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. % ================= %We improve known parallel work bounds for solving the minimum cut problem on dense undirected graphs with poly-logarithmic depth. We give a randomized algorithm that, with high probability, finds a minimum cut in an $m$-edge, $n$-vertex graph with $O(m \log^2 + n \log^4 n)$ work and $O(\log^3 n)$ depth. This result is obtained by parallelizing (a simplified variant of) a recent sequential algorithm of Mukhopadhay and Nanongkai [STOC’20] that exploits a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. % Next version: Mention Karger % (m log n) /eps + n^{1+eps + nlog^4 n
abstract.tex
\begin{abstract}


We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$ %\andres{for any fixed $\epsilon > \log \log n / \log n$}, 
%$\epsilon = \Omega((\log \log n) / \log n)$ 
our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. 
Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOC’20; GMW SOSA'21].  
%
This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. 

% We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m=\Omega(n\log^5 n$) and any constant $\epsilon>0$, our algorithm requires $O(m \log n + n^{1+\epsilon})$ work and $O(\log^3 n)$ depth and succeeds with high probability. 
% Its work matches the best $O(m \log n + n^{1+\epsilon})$ runtime for sequential algorithms [MN STOC’20; GMW SOSA'21].  
% %
% This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. 


%We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For any $\epsilon>0$, our algorithm requires $O(m(\log n)/\epsilon + n^{1+\epsilon} + n\log^4 n)$ work and $O(\log^3 n)$ depth. 
%  For non-sparse graphs ($m=\Omega(n\log^4 n$)), this matches the best $O(m(\log n)/\epsilon + n^{1+\epsilon} + n\log^2 n)$ runtime for sequential algorithms by Mukhopadhyay and Nanongkai [STOC’20] and GMW [SOSA'21],  
%  %
%  and improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by $O(\log^3 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 of Mukhopadhyay and Nanongkai [STOC’20] and GMW [SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. 

% =================

    %We improve known parallel \textit{work} bounds for solving the minimum cut problem on dense undirected graphs with \textit{poly-logarithmic} depth. We give a randomized algorithm that, with high probability, finds a minimum cut in an $m$-edge, $n$-vertex graph with $O(m \log^2 + n \log^4 n)$ work and $O(\log^3 n)$ depth. This result is obtained by parallelizing (a simplified variant of) a recent sequential algorithm of Mukhopadhay and Nanongkai [STOC’20] that exploits a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. 
    
% Next version: Mention Karger 
% (m log n) /eps + n^{1+eps} + nlog^4 n


\end{abstract}
commands.tex
\usepackage{modletters}

\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcommand{\Interest}{Interesting\ }
\newcommand{\interest}{interesting\ }
\newcommand{\heap}{\textsf{Heap}}
\newcommand{\sg}{\mathsf{sg}}

\newcommand{\cost}{\mathsf{Cost}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
%\newcommand{\deg}{\mathsf{deg}}

\newcommand{\bsni}{\bigskip\noindent}

\newcommand{\ZO}{\{0,1\}}
\newcommand{\ZOI}{[0,1]}

\newcommand{\XOR}{\mathsf{XOR}}
\newcommand{\RXOR}{\mathsf{RXOR}}
\newcommand{\IND}{\mathsf{IND}}
\newcommand{\kw}{\mathsf{kw}}
\newcommand{\SPROD}{\mathsf{SPROD}}
\newcommand{\sign}{\mathsf{sign}}

\newcommand{\RD}{\mathsf{RD}}
\newcommand{\SD}{\mathsf{SD}}
\newcommand{\AD}{\mathsf{AD}}
\newcommand{\AL}{\mathsf{AL}}
\newcommand{\cXYZ}{\cX\times\cY\times\cZ}

\newcommand{\ldavg}{\text{\sf AvgLDeg}}
\newcommand{\rdavg}{\text{\sf AvgRDeg}}
\newcommand{\ldmin}{\text{\sf MinLDeg}}
\newcommand{\rdmin}{\text{\sf MinRDeg}}
\newcommand{\Ext}{\text{\sf Ext}}
\newcommand{\leavg}{\text{\sf AvgLExp}}
\newcommand{\reavg}{\text{\sf AvgRExp}}
\newcommand{\lemin}{\text{\sf MinLExp}}
\newcommand{\remin}{\text{\sf MinRExp}}

\newcommand{\neqi}{{\neq i}}



\newcommand{\D}{{\mathsf D}}
\newcommand{\Dsm}{\D_{\mathsf{s}}}
\newcommand{\Dfs}{\D_{\mathsf{fs}}}

\newcommand{\Vplus}{\sfV_{+}}
\newcommand{\Vmax}{\sfV_{\mathrm{mp1}}}
\newcommand{\Nplus}{\cN_{+}}
\newcommand{\Nmin}{\cN_{\mathrm{min}}}
\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
  }}

\newcommand{\supp}{\mathsf{supp}}
\newcommand{\idom}{\mathsf{idom}}
\newcommand{\val}{\mathsf{val}}

\newcommand{\NC}{\mathsf{NC}}
\newcommand{\CAC}{\mathsf{AC}}

\newcommand{\eps}{\varepsilon}


\newcommand{\red}{\color{red}}
\newcommand{\TODO}[1]{{\color{red}TODO: #1}}
\newcommand{\todo}{{\color{red}TODO!}}


\newcommand{\ps}[1]{^{(#1)}}


\newcommand{\DKL}{D_{\mathrm{KL}}}
\newcommand{\E}{\mathop{\mathbf{E}}}



\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\cupdot}{\charfusion[\mathbin]{\cup}{\cdot}}
%\newcommand{\bigcupdot}{\charfusion[\mathop]{\bigcup}{\cdot}}



\usepackage{graphicx}

\newcommand{\class}[1]{\mathbf{#1}}
\newcommand{\co}{\mathrm{co}}
\newcommand{\alg}[1]{\mathrm{#1}}
\newcommand{\lang}[1]{\mathtt{#1}}


% classes (1)

\newcommand{\DTime}{\class{DTime}}
\newcommand{\RTime}{\class{RTime}}
\newcommand{\UTime}{\class{UTime}}
\newcommand{\NTime}{\class{NTime}}
\newcommand{\BPTime}{\class{BPTime}}


\renewcommand{\P}{\class{P}}
\newcommand{\ZPP}{\class{ZPP}}
\newcommand{\RP}{\class{RP}}
\newcommand{\coRP}{\co\class{RP}}
\newcommand{\UP}{\class{UP}}
\newcommand{\coUP}{\co\class{UP}}
\newcommand{\NP}{\class{NP}}
\newcommand{\coNP}{{\co}\class{NP}}
\newcommand{\BPP}{\class{BPP}}
\newcommand{\SigmaP}[1]{\Sigma^{#1}\class{P}}
\newcommand{\PH}{\class{PH}}
\newcommand{\PP}{\class{PP}}
\newcommand{\IP}{\class{IP}}
\newcommand{\OP}{\class{\oplus P}}


\newcommand{\EXP}{\class{EXP}}
\newcommand{\MIP}{\class{MIP}}
\newcommand{\NEXP}{\class{NEXP}}
\newcommand{\coNEXP}{{\co}\class{NEXP}}
\newcommand{\MAEXP}{\class{MA}_\class{EXP}}


% classes (2)

\newcommand{\Ppoly}{\class{P}/\class{poly}}


\newcommand{\DSpace}{\class{DSpace}}
\newcommand{\NSpace}{\class{NSpace}}
\newcommand{\PSPACE}{\class{PSPACE}}

\newcommand{\EXPSPACE}{\class{EXPSPACE}}



% algorithms and proof systems


\newcommand{\DPLL}{\alg{DPLL}}
\newcommand{\CDCL}{\alg{CDCL}}
\newcommand{\OBDD}{\alg{OBDD}}
\newcommand{\cDC}{c\text{-}\alg{DC}}
\newcommand{\oOBDD}{\text{-}\alg{OBDD}}
\newcommand{\pOBDD}{\pi\oOBDD}
\newcommand{\NBP}{1\text{-}\alg{NBP}}
\newcommand{\DPLLL}{\alg{DPLL}_{lin}}
\newcommand{\ResL}{\alg{Res}_{lin}}
\newcommand{\SemL}{\alg{Sem}_{lin}}
\newcommand{\CP}{\alg{CP}}
\newcommand{\NS}{\alg{NS}}
\newcommand{\LK}{\alg{LK}}
\newcommand{\Th}{\alg{Th}}



% languages

\newcommand{\EQ}{\lang{EQ}}

\newcommand{\SAT}{\lang{SAT}}
\newcommand{\CSP}{\lang{CSP}}
\newcommand{\CSPSAT}{\lang{CSP}\text{-}\lang{SAT}}
\newcommand{\PHP}{\lang{PHP}}
\newcommand{\GNI}{\lang{GNI}}
\newcommand{\MAJSAT}{\lang{MAJ}\text{-}\lang{SAT}}
\newcommand{\QBF}{\lang{QBF}}
\newcommand{\BMS}{\lang{BMS}}
\newcommand{\Bit}{\lang{Bit}}
\newcommand{\MBit}{\lang{MonBit}}
\newcommand{\Search}{\lang{Search}}
\newcommand{\KWm}{\lang{KW}^m}
\newcommand{\Next}{\lang{Next}}
\newcommand{\GPHP}{\lang{G\text{-}PHP}}
\newcommand{\Peb}{\lang{Peb}}
\newcommand{\PMP}{\lang{PMP}}
\newcommand{\EC}{\lang{EC}}
\newcommand{\TSR}{\lang{TSR}}



\newcommand{\Bad}{Bad}
\newcommand{\OR}{OR}
\newcommand{\AND}{AND}
\newcommand{\Ind}{\lang{Ind}}



% other

\newcommand{\comp}[1][S]{\overline{#1}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\bool}{\{0, 1\}}

\newcommand{\Img}{\mathop{\mathrm{Im}}}

\DeclareMathOperator*{\Exp}{E}
\DeclareMathOperator*{\rk}{rk}


\newcommand{\floor}[1]{\lfloor #1 \rfloor}
%\newcommand{\ceil}[1]{\lceil #1 \rceil}

\newcommand{\size}[1]{\mathrm{size}}

\newcommand{\reordering}{\mathrm{reordering}}
\newcommand{\weakening}{\mathrm{weakening}}




\newcommand{\set}[2][ ]{\{#2 \ifthenelse{\equal{#1}{ }}{ }{~|~#1}\}}


\DeclareRobustCommand{\rchi}{{\mathpalette\irchi\relax}}
\newcommand{\irchi}[2]{\raisebox{\depth}{$#1\chi$}}

%\newcommand{\comment}[1]{}

\newcommand{\seepage}[2][See]{
    \marginnote{
        \scriptsize {#1} p.~\pageref{#2}
    }
}

\newenvironment{reusable}[2]{
	\ifcsname c@#2_help\endcsname
    \else
	    \expandafter\newcounter{#2_help}
	\fi

    \restatable{#1}{#2}
    \expandafter\label{#2}
    \expandafter\ifnum\value{#2_help} = 0
    	\seepage[For proof see]{#2_app}
    \else
        \seepage{#2}
    \fi
}{
    \endrestatable
}

\newcommand{\reuse}[1]{
	\expandafter\stepcounter{#1_help}
    \expandafter\label{#1_app}
    \csname#1\endcsname*
}

\newcommand{\ngh}{\mathsf{Ngh}}
main.tex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}


\input{preamble.tex}




% ************ BEGIN: DANUPON'S PREAMBLES  *******************

\usepackage{xcolor}

%\newcommand{\ShowComment}{true}
\ifdefined\ShowComment
\newcommand{\danupon}[1]{{\bf \color{green} DANUPON: #1}}
\newcommand{\andres}[1]{{\bf \color{red} ANDRES: #1}}
\else
\newcommand{\andres}[1]{}
\newcommand{\danupon}[1]{}
\fi


\newcommand{\Tres}{T_{rsp}}
\newcommand{\Tcut}{T_{cut}}
\newcommand{\cut}{{\sf cut}}
%\newcommand{\cP}{{\cal P}}
\newcommand{\Gtrunc}{G^{\sf trunc}}
\newcommand{\Gaug}{{\hat G}^{\sf aug}}
\newcommand{\cnt}{{\sf count}}
\newcommand{\fcnt}{{\sf sfcount}}

% ************ END DANUPON'S PREAMBLES *******************


\title{Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs}
%\title{{Weighted Min-Cut is Easy}\\ \large (Sequential, Cut-Query and Streaming Algorithms)}
\author{Andrés López-Martínez \thanks{KTH Royal Institute of technology, Sweden, \texttt{anlm@kth.se}} \and Sagnik Mukhopadhyay \thanks{KTH Royal Institute of technology, Sweden, \texttt{sagnik@kth.se}} \and Danupon Nanongkai \thanks{KTH Royal Institute of technology, Sweden, \texttt{danupon@kth.se}}}

\date{}

\begin{document}





\begin{titlepage}
	\maketitle
	\pagenumbering{roman}
	%\vspace{-.7cm}
	\input{abstract}
	%\setcounter{tocdepth}{3}
	\newpage
	\setcounter{tocdepth}{2}
	\tableofcontents
	%\newpage
	%\listoftheorems
\end{titlepage}

\newpage
\pagenumbering{arabic}

\section{Introduction}
Computing the minimum cut, or min-cut, is a fundamental graph problem. Given a weighted undirected graph $G=(V, E)$, a cut is a set of edges whose removal disconnects $G$. The min-cut problem is to find the cut with minimum total edge weight. Throughout, we let $n=|V|$ and $m=|E|$. Unless stated otherwise, all algorithms are randomized and succeed with high probability.\footnote{We say that an algorithm succeeds with high probability (w.h.p.) if it outputs a correct answer with probability at least $1-1/n^c$ for an arbitrarily large constant $c$.}
%and $\tilde O$ hides $\poly\log(n)$. 

In the sequential setting, nearly-linear time algorithms were known since the breakthrough work of Karger \cite{Kar00}. His algorithm requires $O\left(\frac{m(\log^2 n)\log (n^2/m)}{\log\log n} + n\log^6 n\right)$ time.
%
This bound has been recently improved to  $O(m(\log^2 n)/\log\log n + n\log^6 n)$ \cite{gawrychowski2019minimum,mukhopadhyay2019weighted}. By simplifying the framework of \cite{mukhopadhyay2019weighted}, this was improved to %$O((m\log n + n^{1+\epsilon})/\epsilon + n\log^2 n)$ \andres{
$O(m (\log n)/ \epsilon + n^{1+2\epsilon}(\log^2 n) /\epsilon^2 + n \log^3 n)$ 
%} 
for any $\epsilon>0$ \cite{gawrychowski2020note}. For non-sparse input graphs, e.g. when $m=n^{1+\Omega(1)}$, this bound is the best in the sequential setting. (Note that better bounds exist when the input graph is very sparse or is unweighted and simple \cite{gawrychowski2019minimum, HenzingerRW17, GhaffariNT20}. These cases are relevant to our results.\footnote{For sparse input graphs, the best bound of $O(m\log^2  n)$ is due to \cite{gawrychowski2019minimum} (improving from Karger's $O(m\log^3 n)$ bound). For simple graphs, the best bounds are $O(m \log n)$ and $O(m+n \log^3 n)$ \cite{GhaffariNT20}.})
%
%DANUPON:SAY SOMETHING ABOUT SIMPLE GRAPH \sagnik{Ghaffari, Nowicki and Thorup \cite{GhaffariNT20} $O(m \log n)$ and $O(m+n \log^3 n)$ with randomized algorithms.}})
%There are also results for the special case of unweighted simple graphs. We do not consider these two cases in this paper.}

When it comes to parallel algorithms, no algorithm with nearly-linear work and polylogarithmic depth was known until the recent result by Geissmann and Gianinazzi \cite{10.1145/3210377.3210393}, where they obtain an algorithm with $O(m\log^4 n)$ work and $O(\log^3 n)$ depth. The work of this algorithm is higher than that by Karger's sequential algorithm by an $\Omega(\log n)$ factor, and it was left open in \cite{10.1145/3210377.3210393} whether  a work-optimal algorithm with polylogarithmic depth exists. 



% , with diverse applications ranging from cluster analysis \cite{10.1145/160688.160704} and network reliability \cite{colbourn1987combinatorics} to image processing \cite{graphCutsImageProcessing} and efficient graph parallelization \cite{10.1007/BFb0025872}. While there is a large knowledge base of algorithms that solve the minimum cut problem sequentially (by exactly one core),  %\cite{nagamochi1992linear, 10.1145/234533.234534, Kar00, mukhopadhyay2019weighted}
% the computation of a minimum cut in parallel has recently attracted attention. The motivation for studying the parallel setting rests on the fact that data sets are now growing substantially faster than the increase in capacity of single processors. This means that parallel algorithms are necessary to take full advantage of the gains allowed by Moore's law. 
% % As this problem has many applications and often appears as a subroutine in more complex problems, it is very important to develop fast algorithms that can solve this problem for both small and large data sets. While there is a large knowledge base of algorithms that solve the minimum cut problem sequentially---by exactly one core---\cite{nagamochi1992linear, 10.1145/234533.234534, Kar00, mukhopadhyay2019weighted}, data sets are now growing substantially faster than the increase in capacity of single processors \cite{KAMBATLA20142561}. For this reason, it is of particular interest to develop efficient parallel algorithms for this problem.

% In the sequential setting, nearly-linear time algorithms were known since the breakthrough work of Karger [CITE]. His algorithm requires  $O(m\log^3 n)$ time. When the input graph is not very sparse ($m=\Omega(n\log^3 n \log\log n)$), he could improve his bound to $O(m(\log^2 n)\log (n^2/m)/\log\log n + n\log^6 n)$. 
% %
% Karger's bounds have been recently improved to $O(m \log^2 n)$ \cite{gawrychowski2019minimum} and $O(m(\log^2 n)/\log\log n + n\log^6 n)$ \cite{gawrychowski2019minimum,mukhopadhyay2019weighted}. By simplifying the framework of \cite{mukhopadhyay2019weighted}, the latter bound was improved to $O(m(\log n)/\epsilon + n^{1+\epsilon} + n\log^2 n)$ for any $\epsilon>0$ \cite{gawrychowski2020note}. (Also see [CITE] for results for unweighted simple graphs.) 


\paragraph{Our results.} We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For any %$\epsilon>0$ 
$\epsilon \geq 1/ \log n$, our algorithm requires $O(\log^3 n)$ depth while its work is
%$O((m\log n + n^{1+\epsilon})/\epsilon + n\log^4 n)$ work and $O(\log^3 n)$ depth. 
%$$O\left(\frac{m \log n + n^{1+\epsilon}}{\epsilon}+\log^5 n\right)\mbox{work and $O(\log^3 n)$ depth}$$ 
%$$O\left(\frac{m \log n + n^{1+\epsilon}}{\epsilon}+n \log^5 n\right).$$ 
%
%\andres{
$$O\left(\frac{m \log n}{\epsilon} + \frac{n^{1+2\epsilon}\log^2 n}{\epsilon^2} + n \log^5 n\right)$$
%}
For non-sparse graphs ($m\geq cn\log^3 n\log \log n$ for some large constant $c$), the work of our algorithm matches the best $O(m (\log n)/ \epsilon + n^{1+2\epsilon}(\log^2 n)/\epsilon^2 + n \log^3 n)$ runtime for sequential algorithms \cite{mukhopadhyay2019weighted,gawrychowski2020note}.\footnote{This is because $m (\log n) / \epsilon + n^{1+2\epsilon}(\log^2 n) /\epsilon^2 > n \log^5 n$ when $m\geq cn\log^3 n\log \log n$. Otherwise, $m (\log n) / \epsilon\leq  n \log^5 n$ implies that $\epsilon\geq c (\log\log n)/\log(n)$. But then $n^{1+2\epsilon}(\log^2 n) /\epsilon^2\geq n^{1+2c \log\log(n)/\log(n)}\log^2 n > n\log^{5} n$ for large enough constant $c$ (note that $\epsilon<1$ since the claim is obvious otherwise). We thank Pawe{\l} Gawrychowski for the clarification regarding the bound in \cite{gawrychowski2021note}.}  
When $m=n^{1+\Omega(1)}$, the work of our algorithm can be simplified to $O(m\log n)$ and improves the previous best work by Geissmann and Gianinazzi \cite{10.1145/3210377.3210393} by an $\Omega(\log^3 n)$ factor  while matching the depth of their algorithm. 


{\em Remark:} Concurrently and independently from this paper,  \cite{AndersonB2021} recently achieved a parallel algorithm with $O(\log^3 n)$ depth and $O(m\log^2 n)$ work by parallelizing the sequential algorithm of \cite{gawrychowski2019minimum}. The work of this algorithm is smaller than ours for sparse graphs ($m=O(n\log^3 n)$). This is work-optimal when $m=O(n \log^2 n)$ (but not when $m=\omega(n \log^2 n)$).\footnote{When $m=n\log^2(n)g(n)$ for some growing function $g$, we have $\frac{m \log n}{\epsilon}  + \frac{n^{1+2\eps}\log^2 n}{\eps^2}+n\log^3 n< m \log^2 n$ by setting $\epsilon$ to $c(\log\log(g(n))/\log n$ for some constant $c$.}  Table \ref{table:1} compares our result with other results.

\begin{table}[t]
\centering
\label{table:1}
\begin{tabular}{|l|c|c|}
\hline
%\textbf{Reference} & \multicolumn{2}{|c|}{\textbf{Complexity}} & \textbf{Remark}\\
\textbf{Source} & \textbf{Work} &  \textbf{Remark}\\
\hline
%\multicolumn{4}{|c|}{Sequential}\\\hline
%\multicolumn{4}{|c|}{Parallel}\\\hline
%& \textbf{Work} & \textbf{Depth} &\\\hline
\cite{10.1145/3210377.3210393} & $O(m \log^4 n)$ & Old record\\
\hline
%Here & $O(m \log^2 n + n \log^4 n)$ & $O(\log^3 n)$ & New record\\
Here & $O(m \log n + n^{1+\epsilon})$ & work-optimal on\\
(for constant $\epsilon$)& & non-sparse graphs\\
\hline
%\multicolumn{4}{|c|}{Work-optimal}\\\hline
\cite{AndersonB2021} & $O(m \log^2 n)$ & work-optimal on\\
(independent)& & sparse graphs\\

\hline
\end{tabular}
\caption{Bounds for randomized parallel algorithms computing the minimum cut with high probability. All algorithms require $O(\log^3 n)$ depth.}
\end{table}

% \begin{table}
% \caption{Bounds for randomized parallel algorithms computing the minimum cut with high probability.}% and $O(\log^3 n)$ depth.}
% \label{table:1}
% \begin{tabular}{|l|c|c|c|}
% \hline
% %\textbf{Reference} & \multicolumn{2}{|c|}{\textbf{Complexity}} & \textbf{Remark}\\
% \textbf{Source} & \textbf{Work} & \textbf{Depth} & \textbf{Remark}\\
% \hline
% %\multicolumn{4}{|c|}{Sequential}\\\hline
% %\multicolumn{4}{|c|}{Parallel}\\\hline
% %& \textbf{Work} & \textbf{Depth} &\\\hline
% \cite{10.1145/3210377.3210393} & $O(m \log^4 n)$ & $O(\log^3 n)$ & Old record\\
% %Here & $O(m \log^2 n + n \log^4 n)$ & $O(\log^3 n)$ & New record\\
% Here & $O(\frac{m \log n + n^{1+\epsilon}}{\epsilon}+\log^5 n)$ & $O(\log^3 n)$ & work-optimal on\\
% & & & non-sparse graphs\\
% %\hline
% %\multicolumn{4}{|c|}{Work-optimal}\\\hline
% \cite{AndersonB2021} & $O(m \log^2 n)$ & $O(\log^3 n)$ & work-optimal on\\
% (independent)& & & sparse graphs\\

% \hline
% \end{tabular}
% \end{table}



To achieve our result, one challenge is to first solve the problem {\em approximately}. This is crucial because all known nearly-linear time sequential algorithms require to compute the so-called {\em skeleton} and to compute the skeleton we need an $O(1)$-approximate value of the min-cut. 
%
While a linear-time $(2+\epsilon)$-approximation algorithm was known in the sequential setting \cite{matula1993linear}, no $O(1)$-approximation algorithm that requires polylogarithmic depth and work less than the exact algorithm of \cite{10.1145/3210377.3210393} was known in the parallel setting. 
%
In this paper, we show a $O(1)$-approximation algorithm with $O(m\log n+n \log^5 n)$ work and $O(\log^3 n)$ depth. The algorithm can be modified to obtain a $(1 + \eps)$-approximation of the min-cut (for any small constant $\eps$) without any change in the performance guarantee. This algorithm might be of independent interest. 

Another bottleneck in the previous parallel algorithm of \cite{10.1145/3210377.3210393} is solving the so-called {\em two-respecting cut problem}, where the randomized %\danupon{deterministic, right?} \sagnik{No.}
algorithm of \cite{10.1145/3210377.3210393} requires $O(m\log^3 n)$ work and $O(\log^2 n)$ depth. The work does not match the then-best time complexity of  $O(m\log^2 n)$ in the sequential setting \cite{Kar00}. In this paper, we obtain a work-optimal algorithm for this problem. Our algorithm is deterministic and requires %$O\left(\frac{m \log n + n^{1+\epsilon}}{\epsilon}+n\log^2 n\right)$ \andres{
$O(m / \epsilon + n^{1+2\epsilon}(\log n)/\epsilon^2 + n \log n)$ 
%} 
%\andres{The last term slightly improves the sequential algorithm. Leave it, or bound it with $n \log^2 n$?}
work and $O(\log^2 n)$ depth. Its work matches that by the sequential algorithm of \cite{mukhopadhyay2019weighted,gawrychowski2020note}. To do this, we parallelize the algorithm of \cite{mukhopadhyay2019weighted} and its simplification in \cite{gawrychowski2020note}, which exploit a connection between the 2-respecting min-cut problem and 2-dimensional orthogonal range searching.  



\paragraph{Organization.} We review the necessary prerequisites in Section \ref{sec:prelims}. In Section \ref{sec:approx_mincut}, we provide the parallel algorithm for approximating min-cut in a weighted graph. Finally, in Section \ref{section.parallelMinimumCuts} we design the parallel algorithm for computing the exact minimum cut in a weighted graph.

% \section{TO REMOVE?}


% We consider \textit{shared-memory} parallel algorithms for computing the minimum cut. Our work is based on two of the fastest known sequential min-cut algorithms, Karger's algorithm \cite{Kar00} and Mukhopadhyay and Nanongkai's (MN) algorithm \cite{mukhopadhyay2019weighted}. The former achieved the best complexity bounds for weighted graphs since its discovery more than two decades ago, and the latter is a very recent improvement when the input graph is not extremely sparse or dense. To get slightly improved bounds, in this paper we consider the simplified variant \cite{gawrychowski2020note} of MN's algorithm by Gawrychowski, Mozes, and Weimann (GWM).  

% %Karger's algorithm produces a minimum cut on an $m$-edge $n$-vertex graph in $O(m \log^3 n)$ time. This result stood as the fastest min-cut algorithm for more than two decades, until very recently Mukhopadhyay and Nanongkai were able to obtain an algorithm with running time $O(m \log^2 n + n \log^5 n)$, which is an improvement when the input graph is not extremely sparse or dense.

% Karger's algorithm exploits a connection between minimum cuts and approximate maximum packings of spanning trees, which serve to partition the problem into two optimization sub-problems: \textit{tree packing} and \textit{minimum 2-respecting cut}. The \textit{tree packing} problem asks to find an appropriate set of spanning trees such that the minimum cut of the graph cuts at most two edges from at least one of the trees. %We call this problem the \textit{tree packing} or simply \textit{packing} problem.
% %Using random edge-sampling techniques and a classical packing method of optimization theory, Karger already showed that this problem can be solved in parallel. %with $W_{pack} = O(m \log^3 n)$ work and $D_{pack} = O(\log^3 n)$ depth.
% %sequentially in $T_{pack} = O(m + n \log^3 n)$ time, and can be easily parallelized with $W_{pack} = \tilde{O}(m)$ work and $D_{pack} = O(\log^3 n)$ depth ($\tilde{O}(f)$ denotes $O(f \cdot polylog(f))$. 
% % Mention here that Karger was able to parallelize it.
% For the \textit{minimum 2-respecting cut} problem we are given a spanning tree of the input graph and we are tasked with finding a minimum cut that contains at most two edges of---\textit{2-respects}---the tree. 
% %The second sub-problem and core subroutine of the algorithm is the \textit{minimum 2-respecting cut} problem. Given a spanning tree of the input graph, it asks for the minimum cut that contains at most two edges of---\textit{2-respects}---the tree. 
% %For a long time it remained open to parallelize this problem with poly-logarithmic depth. %It was until recently that Geissmann and Gianinazzi \cite{10.1145/3210377.3210393} were able to obtain a $W_{rsp} = O(m \log^3 n)$ work and $D_{rsp} = O(\log^2 n)$ depth parallel algorithm for the minimum 2-respecting cut problem. 

% % Mention here that G&G were able to parallelize it. 
% The algorithm of Mukhopadhyay and Nanongkai obtains a better run-time than Karger's due to an improved procedure for the minimum 2-respecting cut problem. They exploit simple structural properties that arise when the input spanning tree is a path that can then be generalized to handle any tree. Mukhopadhyay and Nanongkai further apply their new approach to minimum cuts in the cut-query, streaming, and distributed models. In this paper, we build on these results by giving a parallel implementation of the (simplified) algorithm that %requires the same number of operations as the best sequential algorithm (i.e., is work-optimal) for non-sparse graphs. It has 
% has no overhead compared to the sequential one (i.e. it is work-optimal). %, with work complexity $O(m \log n + n \log^3 n)$ and depth complexity $O(\log^2 n)$.  
% %sampling and counting points in a two-dimensional range. % Say that it has proven to be useful for more settings like cut query and streaming and that we build on those results by giving a parallel version of the algorithm. 
% We achieve this by parallelizing a core geometric data structure and by carefully combining previous results in parallel algorithms. % and formally argue that such combination leads to the desired complexity.  

% We identify one main challenge for obtaining a work-optimal parallel minimum cut algorithm. Karger already showed that the tree packing problem can be solved in parallel. The required work, however, is a poly-logarithmic factor far from optimal. If we combine our parallelization of Mukhopadhyay and Nanongkai's algorithm with Karger's tree packing parallel procedure, the latter's work complexity becomes the new bottleneck to overcome. We solve this challenge by giving a constant-factor min-cut approximation algorithm that has better work complexity than previously known. Within Karger's framework, this can be used to find a (correct) sparse subgraph of the input graph on which we can pack spanning trees efficiently and our algorithm may succeed with optimal work (on non-sparse graphs).  
% %Our improved algorithm finds a $(1+\epsilon)$-approximation algorithm with high probability in $O(m \log n)$ work and $O(\log^3 n)$ depth. 

% % observing that in sampling weighted edges in Karger's original procedure, only a small fraction of the weight must actually be considered. This works because the sampling comes with guarantees on the new size of the minimum cut. Our improved packing algorithm requires the same depth as Karger's but only $\tilde{O}(m \log^2 n)$ work. 



% % In the parallel setting, Karger was able to parallelize every step of his algorithm, except for his minimum 2-respecting cut procedure. For a long time, this remained an open problem. It was until recently, that Geissmann and Gianinazzi \cite{10.1145/3210377.3210393} were able to parallelize Karger's sophisticated minimum 2-respecting cut procedure, achieving the best known parallel complexity bounds for the min-cut problem to date. However, the question of whether there existed a work-optimal minimum cut algorithm with poly-logarithmic depth remained open. Based on the improved sequential min-cut algorithm of Mukhopadhyay and Nanongkai, this work gives an affirmative answer to the question. 
% % %Based on the latest sequential improvement to Karger's algorithm, this work provides an affirmative answer to the question. %answers this question affirmatively. %question of whether this sequential improvement also leads to an improved parallel minimum cut algorithm. 

% %In this paper we give improved parallel algorithms for both the tree packing and minimum 2-respecting cut problems. Our tree packing procedure 

% \subsection{Preliminaries}
% \subsubsection{Graphs} 
% We consider an \textit{undirected weighted graph} $G = (V, E)$ with vertices, or nodes $V$, edges $E$, and positive integer edge weights\footnote{Our results extend to graphs with rational edge weights if we multiply all edge weights by their least common denominator---which can also be used for real valued edge weights, as an irrational number may be approximated arbitrarily well by a rational. See also \cite[Sec. 3.1]{Kar00}.} 
% $w: E \to \mathbb{Z}^+$. We use the convention of writing $n = |V|$ and $m = |E|$. Unless otherwise stated, vertices are assumed to be indexed from 0 to $n - 1$. An edge from $E$ is denoted by $(u, v)$, with $u$ and $v$ two distinct nodes in $V$. %To represent graphs in our algorithms, unless otherwise stated, we assume they are given as an \textit{adjacency list}---an array of arrays, each of which corresponds to a vertex in the graph, and consists of the indices of its adjacent vertices. 
% We also consider unweighted \textit{multigraphs}, where possibly multiple edges connecting the same pair of distinct vertices---parallel edges---are allowed. 

% In this work we also consider \textit{rooted trees}. For a tree $T = (V, E_T)$ rooted at $r$, we use $par(v)$ to denote the parent of a node $v \in V$ with $v \neq r$, and use $u^\downarrow$ to denote the set of nodes in the subtree rooted at $u \in V$, where $size(u)$ is used to denote the cardinality of $u^\downarrow$. For \textit{binary trees} we use $lc(u)$ and $rc(u)$ to denote the left and right children of an inner node $u$, respectively. 

% \subsubsection{Cuts}
% Let $G = (V, E)$ be a graph, a \textit{cut} is a partition of $V$ into two non-empty sets $S$ and $\overline{S}$, %\footnote{Where $\overline{S}$ is shorthand notation for $V \setminus S$; that is, the complement of $S$ in $V$.},
% and is denoted by $(S, \overline{S})$. The \textit{edge-cut} induced by $S$, denoted by $\mathcal{C}(S)$, is the set of edges $(u, v) \in E$ such that $u \in S$ and $v \in \overline{S}$. For simplicity, in this work we unambiguously refer to a cut by its induced edge-cut. We use $C(S)$ to denote the total weight of edges in $\mathcal{C}(S)$ (note the difference in font), which we call the \textit{value} or \textit{size} of the cut. In the \textit{minimum cut} problem, we wish to find a cut $\mathcal{C}(S)$ that yields a minimum value for $C(S)$. Such a cut is called the \textit{minimum cut} or \textit{min-cut} of $G$. We use $\lambda$ to denote the value of the minimum cut over all $S \subset V$.

% \subsubsection{Model of Computation}
% %In this thesis, we use the Parallel Random Access Machine (PRAM) model for analyzing parallel algorithms. More precisely, we consider the \textit{exclusive-read exclusive-write} (EREW) and \textit{concurrent-read exclusive-write} (CREW) variants. To describe and reason about the complexity of our PRAM algorithms at a higher-level of abstraction, we use the \textit{work-depth} model. In this model, the performance of an algorithm is determined by its \textit{work}---the total number of operations required---and its \textit{depth}---the number of time steps taken. All our results are thus stated in the work-depth model, whilst specifying the underlying PRAM variant.

% %%% Slightly more informative (open)
% We use the Parallel Random Access Machine (PRAM) model \cite{fortune1978parallelism} as our formal model of computation for analyzing parallel algorithms. To measure the cost of our PRAM algorithms and describe them on a higher-level of abstraction, we use the \textit{work-depth} model \cite{shiloach1982n2log, GuyEBlelloch}, sometimes called \textit{work-span} model \cite{cormen2009introduction} or \textit{work-time framework} \cite{10.5555/133889}. An algorithm in this model does not assume any specific number of processors but rather is seen as an ordered sequence $S$ of operation sets, where each set $s_i \in S$ may include any number of unit-cost operations to be executed simultaneously in parallel at step $i$ \cite{10.5555/133889}. This allows algorithms to be expressed at a high-level---similarly to sequential algorithms---through the inclusion of parallel loops. Under the work-depth model, the performance of a PRAM algorithm can be measured by two parameters---\textit{work} $W(n)$ and \textit{depth} $D(n)$. The work $W(n)$ is the total number of operations required by the algorithm as a function of the input size $n$, and the depth $D(n)$ is defined as the number of parallel time steps needed by the algorithm assuming an unbounded number of processors are available. 
% %%% (close)

% \subsubsection{Efficiency}
% Depending on the application, it is generally preferred to obtain slow algorithms with low work rather than faster algorithms that perform many operations. Let $T(n)$ be the running time of the fastest sequential algorithm for a given problem on an input of size $n$. We say that a parallel algorithm is \textit{work-optimal}\footnote{Other authors call this \textit{work-efficient} \cite{GuyEBlelloch, shun2017shared}.} if $W(n) = \Theta(T(n))$ \cite{10.5555/133889}. In other words, an algorithm is work-optimal if it performs the same number of operations---up to a constant---as the best known sequential algorithm for the same problem. 

% \subsubsection{Randomization}
% Most of the algorithms discussed in this work rely on randomization. We say that a result holds with high probability (\textit{w.h.p.}) if, for an input of size $n$, it produces a correct result with probability at least $1 - n^{-c}$, where $c$ is an arbitrary constant greater than zero. 

% \subsection{Previous Work}
% There is a long history of algorithms that compute the minimum cut of an $m$-edge, $n$-vertex graph $G$. The first approaches were based on the maximum s-t flow problem. The well-known \textit{max-flow min-cut} theorem \cite{ford2009maximal} states that the minimum s-t cut can be obtained by finding the maximum s-t flow in the same network. In \cite{gomory1961multi} Gomory and Hu showed how to solve the min-cut problem with $n - 1$ flow computations. This was further improved by Hao and Orlin \cite{HAO1994424}, who obtained a $O(mn \log(n^2/m))$--time deterministic min-cut algorithm by relying on a single flow computation.

% Drifting apart from the maximum s-t flow problem, better bounds were achieved
% based on the idea of \textit{edge contraction}. Using this approach via \textit{connectivity certificates}, Nagamochi and Ibaraki \cite{doi:10.1137/0405004} developed a deterministic algorithm for undirected, weighted graphs with a run time of $O(mn + n^2\log n)$.
% Progress continued with randomized algorithms. The now considered classic result to compute the minimum cut with high probability is a very simple edge-contraction algorithm by Karger, which randomly contracts edges until two vertices remain \cite{KargerGlobalMincutsRNC}. An improvement due to Karger and Stein \cite{10.1145/234533.234534} achieves a run time of $O(n^2 \log^3 n)$, which can be easily parallelized with the same work and $O(\log^3 n)$ depth.

% Until recently, the best known sequential bounds for finding the minimum cut for weighted graphs belonged to Karger's near-linear $O(m \log^3 n)$ time algorithm (with some tricks, he also gave an improved time bound of $O(m \frac{\log^2 n \log(n^2/m)}{\log \log n} + n \log^6 n)$) \cite{Kar00}. 
% %Given a spanning tree $T$ of $G$, the core procedure of the algorithm is a subroutine that finds the minimum cut that contains at most two edges of (2-respects) $T$---this is referred to as the \textit{minimum 2-respecting cut problem}. 
% A simplification of Karger's algorithm achieving the same $O(m \log^3 n)$ complexity was recently developed by Bhardwaj, Lovett, and Sandlund \cite{bhardwaj_et_al:LIPIcs:2020:12259}. 
% Better sequential bounds to Karger's were known, but only under the assumption that the input graph is \textit{simple} (i.e. undirected, unweighted, and without parallel edges). In this setting, Henzinger, Rao and Wang \cite{10.5555/3039686.3039811} achieve an $O(m \log^2 n \log \log^2 n)$--time deterministic algorithm, which was later improved by Ghaffari, Nowicki and Thorup \cite{10.5555/3381089.3381166} to $O(m \log n)$ and $O(m + \log^3 n)$ with randomization.

% In the parallel setting, a simpler (but less efficient) variant of Karger's near-linear time algorithm can be parallelized with optimal $O(n^2 \log n)$ work and $O(\log^3 n)$ depth \cite{Kar00}. In a recent development, Geissmann and Gianinazzi \cite{10.1145/3210377.3210393} succeed in parallelizing both the data structure and the computations required by Karger's more complicated near-linear time algorithm. Their procedure stands as the current state of the art and computes the minimum cut with high probability using $O(m \log^4 n)$ work and $O(\log^3 n)$ depth. In \cite{10.5555/3381089.3381166}, Ghaffari, Nowicki, and Thorup were able to obtain a parallel algorithm with an improved work bound of $O(m \log n + n \log^4 n)$ while achieving the same $O(\log^3 n)$ depth complexity, but only by assuming a simple graph as input.

% As the latest development in randomized and sequential min-cut algorithms for the weighted case, following the same general outline of Karger's approach, Mukhopadhyay and Nanongkai \cite{mukhopadhyay2019weighted} recently obtained a $O(m \frac{\log^2 n}{\log \log n} + n \log^6 n)$--time randomized algorithm. The main improvement is a $O(m \log n + n\log^4 n)$--time algorithm for solving the minimum 2-respecting cut problem. To achieve this, they essentially reduce the problem to counting and sampling points from a 2-d orthogonal range, for which they construct efficient data structures based on a space-compressed \textit{range tree} \cite{doi:10.1137/0217026}. %This reduction is then made efficient by exploiting simple structural properties that arise when $T$ is a path, which Mukhopadhyay and Nanongkai then generalize to handle any case. 
% A deterministic simplification of their algorithm with slightly better $O(m \log n + n \log^3 n)$ time complexity was recently obtained by Gawrychowski, Mozes and Weimann \cite{gawrychowski2020note}. They also show that for graphs with $m = \Omega(n^{1+\epsilon})$ and $\epsilon > 0$, the running time can be further improved to $O(m \log n + n^{1+\epsilon})$, which dominates all previous sequential algorithms for non-sparse graphs. 

% \subsection{Our contribution}
% For a weighted graph $G$ with $n$ nodes and $m$ edges, our main contribution is a randomized parallel minimum cut algorithm that has near-linear work $O(m \log^2 n + n \log^4 n)$ and low depth $O(\log^3 n)$ and returns the correct result with high probability. When the input graph is dense, we show how to improve the work bound to $O(m \log n + n^{1+\epsilon})$ for any fixed $\epsilon > 0$. For $m = \Omega(n^{1+\epsilon})$, the best sequential algorithm \cite{gawrychowski2020note} for the minimum cut problem requires the same number of operations (up to a constant factor). Our new algorithm, presented in Section \ref{section.parallelMinimumCuts}, is thus work-optimal when the input graph is not too sparse. Following Karger's tree packing framework, as part of our solution, we present the following parallel algorithms: 
% \begin{enumerate}
%     \item Given a spanning tree of the input graph, in Section \ref{section.parallel2Respecting} we show how to find a minimum 2-respecting cut with $O(m \log n + n \log^3 n)$ work and $O(\log^2 n)$ depth. This is a parallelization of GMW's simplification \cite{gawrychowski2020note} of MN's 2-respecting min-cut algorithm \cite{mukhopadhyay2019weighted}. The best previous algorithm \cite{10.1145/3210377.3210393} with poly-logarithmic depth has $O(m \log^2 n)$ work and $O(\log^2 n)$ depth complexities. 
    
%     \item Given a weighted graph, in Section \ref{section.parallelPacking} we show how to compute an approximate maximum tree packing with $O(m \log n + n \log^* n)$ work and $O(\log^3 n)$ depth. This improves in a $O(\log^2 n)$ factor the best-known work bound given by Karger in \cite{Kar00}. The main contribution, presented in Section \ref{sec:approx_mincut}, is a $O(m \log n + n \log* n)$ work and $O(\log^3 n)$ depth parallel $(1 + \epsilon)$-approximation min-cut algorithm.  We use this algorithm to find a correct edge-sampling probability with which to construct a sub-graph of $G$ that preserves the value of the min-cut with arbitrary precision. 
% \end{enumerate}

\section{Preliminaries} \label{sec:prelims}
In this section, we introduce the model of computation and briefly state the main ideas of Karger's \cite{Kar00} and Mukhopadhyay-Nanongkai's \cite{mukhopadhyay2019weighted} min-cut algorithms. Then we review two important concepts---graph skeletons and connectivity certificates---that are extremely useful for our algorithms.

\subsection{Model of Computation}
We use the \textit{work-depth} model \cite{shiloach1982n2log, GuyEBlelloch} (sometimes called \textit{work-span} model \cite{cormen2009introduction} or \textit{work-time framework} \cite{10.5555/133889}) to design and analyze the theoretical performance of our algorithms. The \textit{work} of an algorithm is defined as the total number of operations used, similar to the time complexity in the sequential RAM model. And the \textit{depth} is the length of the longest sequence of dependent operations. We assume concurrent reads and writes are supported. 
By Brent's scheduling theorem \cite{10.1145/321812.321815}, an algorithm with work $W$ and depth $D$ takes $O(W/p + D)$ time when $p$ processors are available. A parallel algorithm is \textit{work-optimal} if it performs the same number of operations---up to a constant---as the best known sequential algorithm for the same problem.

\subsection{Karger's Minimum Cut Algorithm}
The basic idea behind Karger's randomized algorithm is to exploit a connection between minimum cuts and \textit{greedy} packings of spanning trees. 

\begin{definition}[(Greedy) tree packing]
Let $G = (V, E)$ be a weighted graph. A \textit{tree packing} $\mathcal{S}$ of $G$ is a multiset of spanning trees of $G$, where each edge $e \in E$ is loaded with the total number of trees containing $e$. We say that $\mathcal{S} = (T_1, \ldots, T_k)$ is a \textit{greedy tree packing} if each $T_i$ is a minimal spanning tree with respect to the loads induced by $\{T_1, \ldots, T_{i-1}\}$ and no edge has load greater than the weight of that edge.
\end{definition}

Such a packing $\mathcal{S}$ of $G$ has the important property that the minimum cut in $G$ 2-respects (cuts at most 2 edges of) at least a constant fraction of the trees in $\mathcal{S}$. Therefore, if we try out trees from the packing and, for each of them, find the minimum cut that 2-respects it, we will eventually stumble upon the minimum cut of $G$. To make this efficient, Karger uses random sampling techniques to construct a sparse subgraph $H$ of $G$ on which a greedy tree packing can be computed in less time. %We call graph $H$ a \textit{cut-certificate} of $G$. 
The schematic description of the algorithm is given below.

%This completes the intuition behind Karger's algorithm. %It consists of two phases: (1) a tree-packing phase, where we compute a cut-certificate of $G$ and pack appropriately many spanning trees; and (2) a cut-finding step, where we find a 2-respecting min-cut which respects a tree from the packing produced in the first phase. 

\begin{center}
  \centering
  \begin{minipage}[H]{0.8\textwidth}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\State Find a sparse subgraph $H$ of $G$ that preserves the min-cut with arbitrary precision.
    %whose min-cut is small, that approximately preserves the value of the min-cut of $G$. 
\State Find a tree packing in $H$ of weight $O(\lambda') = O(\log n)$, that \textit{w.h.p.} contains a tree that 2-constrains the min-cut of $H$.
\State For each tree in the packing, find the smallest cut in $G$ that 2-respects the tree.
\end{algorithmic}
\caption[Caption for LOF]{Schematic of Karger's algorithm.} \label{algo.schematicMinCut}
\end{algorithm}
\end{minipage}
\end{center}
%From earlier introduced terminology, we identify steps 1 and 2 of the schematic as conforming to the tree packing 
We refer to steps 1 and 2 from the schematic as the \textit{tree packing step}, and to the problem of finding a 2-respecting min-cut in step 3 we refer as the \textit{cut-finding step}. 

\subsection{MN's 2-Respecting Min-Cut Algorithm} \label{section.Background.subsection.MNAlgorithm}
%We use this section to give some intuition behind 
We now briefly describe the algorithm of Mukhopadhyay and Nanongkai for serving the cut-finding step.

Let $T$ be a spanning tree of the input graph $G$. The algorithm rests on the fact that the cut determined by tree edges $e$ and $f$ is unique, and consists of edges $(u, v) \in G$ such that exactly one of $e$ and $f$ belongs to the $uv$-path in $T$. Let $cut(e,f)$ denote the value of such cut for any pair $e, f \in T$. 

Assume for now that $T$ is a path. In matrix terms, the minimum 2-respecting cut problem can be restated as finding the smallest element in the matrix $M$ of dimension $(n - 1) \times (n - 1)$ where the $(i, j)$-th entry of $M$ is determined by $M[i, j] = cut(e_i, e_j)$, with $e_i$ and $e_j$ the $i$-th and the $j$-th edges of $T$, respectively. A key insight of Mukhopadhyay and Nanongkai is in observing that the matrix $M$ satisfies a monotonicity property (see \cite[Sec. 3.1]{mukhopadhyay2019weighted} or \cite[Sec. 3.2]{gawrychowski2020note} for more details). One can take advantage of this property to find the minimum entry of $M$ in time more efficient that %more efficiently than 
inspecting up to $O(n^2)$ entries in the worst case. 
%This makes computing the minimum entry in $M$ more efficient than inspecting up to $O(n^2)$ entries in the worst case. 

This approach is generalized to handle any tree $T$ by decomposing it into a set $\mathcal{P}$ of edge-disjoint paths \cite{SLEATOR1983362}, each of which satisfies a monotonicity property (when considering all other tree edges as collapsed). Observe that it can also happen that the two tree edges $e$ and $f$ with minimum value $cut(e, f)$ each belong to a different path in $\mathcal{P}$. Hence, the algorithm must also consider pairs of paths, of which there can be $O(n^2)$ many. But another significant contribution of Mukhopadhyay and Nanongkai is in observing that one does not need to consider every pair of paths $P, Q \in \mathcal{P}$. They show that inspecting only a small subset of path pairs suffices to find the minimum 2-respecting cut of $T$ in $G$. %(See Figure \ref{fig:crossAndDownInterest} for an illustration of the notion of \textit{interest}.)

% \begin{definition}[Interest \cite{mukhopadhyay2019weighted, gawrychowski2020note}]
% Let $T_e$ denote the sub-tree of $T$ rooted at the lower endpoint (furthest from the root) of $e$, and let $\mathcal{P}$ be a collection of edge-disjoint paths in $T$.
% \begin{itemize}
%     \item An edge $e \in T$ is said to be \textit{cross-interested} in an edge $f \not\in T \setminus T_e$ if $w(T_e) < 2w(T_e, T_f)$. 
%     \item An edge $e \in T$ is said to be \textit{down-interested} in an edge $f \in T_e$ if $w(T_e) < 2w(T_f, T \setminus T_e)$.
%     \item An edge $e \in T$ is said to be interested in a path $p \in \mathcal{P}$ if it is cross-interested or down-interested in some edge of $p$. 
%     \item Two paths $p, q \in \mathcal{P}$ are said to be an \textit{interested path pair} if $p$ has an edge interested in $q$ and vice versa.
% \end{itemize}
% \end{definition}

On a very high level, the algorithm can be summarized into three steps as in the schematic below.  

\begin{center}
  \centering
  \begin{minipage}[H]{0.8\textwidth}
\begin{algorithm}[H]
\begin{algorithmic}[1]
    %\State Compute the 1-respecting min-cut of $T$ in $G$.
    \State Decompose $T$ into a set of edge-disjoint paths $\mathcal{P}$. %satisfying Property \ref{theorem:treeDecomposition}.
    \State Compute the 2-respecting min-cut for single paths in $\mathcal{P}$.
    %\State Compute a centroid decomposition of $T$.
    %\State Find interested edge-pairs and corresponding path-pairs.
    \State Compute the 2-respecting min-cut among path-pairs.
\end{algorithmic}
\caption[Caption for LOF]{Schematic of MN's algorithm.} \label{algo.schematic2RespMinCut}
\end{algorithm}
\end{minipage}
\end{center}

In Section \ref{section.parallel2Respecting} we formally argue that each step of the algorithm can be parallelized with optimal work and low depth. 

\subsection{Graph Sparsification}
In this section we review useful sparsification tools introduced by Karger \cite{Karger:Thesis} and Nagamochi and Ibaraki \cite{nagamochi1992linear} that are used in both our exact and approximation min-cut algorithms. 

\subsubsection{Graph Skeletons}
Let $G = (V, E)$ be an unweighted multigraph. A \textit{skeleton} is defined by Karger \cite{10.2307/3690490, Karger:Thesis}, as a subgraph of $G$ on the same set of vertices, obtained by placing each edge $e \in G$ in the skeleton independently with probability $p$. If $G$ is weighted, a skeleton can be constructed by placing each edge $e \in G$ in the skeleton with weight drawn from the binomial distribution with probability $p$ and the number of trials the weight $w(e)$ in $G$.

An important result %by Karger 
that rests at the core of our algorithms is the following:

\begin{theorem}[\cite{10.2307/3690490, Karger:Thesis}]
\label{theorem:samplingTheorem} 
Let $G$ be a weighted graph with minimum cut $\lambda$ and let $p = 3(d + 2)(\log n)/(\eps^2 \gamma \lambda)$ where $\eps \leq 1$, $\gamma \leq 1$ and both $\eps$ and $\gamma$ are $\Theta(1)$. Then, a skeleton $H$ of $G$ constructed with probability $p$ satisfies the following properties with high probability: 
\begin{enumerate}
    \item The minimum cut in $H$ has value $\lambda'$ within $(1 \pm \eps)$ times its expected value $p\lambda$, which is $\lambda' =  O(\log n / \eps^2)$. 
    \item The value of the minimum cut in $G$ corresponds (under the same vertex partition) to a $(1 \pm \eps)$ times\footnote{This statement hides the fact that the approximation is also scaled by the inverse of $p$. For more details see \cite[Lemma 6.3.2]{Karger:Thesis}} minimum cut of $H$.
\end{enumerate}
\end{theorem}

In simpler terms, by sampling edges of $G$ with probability $p = O(\log /\lambda)$, we obtain a graph $H$ where (i) the min-cut is $O(\log n)$, and (ii) the minimum cut of $G$ corresponds to (under the same vertex partition) $(1\pm \eps)$-times the minimum cut of $H$.

\subsubsection{Connectivity Certificates}
A related concept of importance is the \textit{sparse k-connectivity certificate}. We use this in our algorithms to bound the total size of a graph. Unlike a skeleton, where all cuts are approximately preserved, the $k$-connectivity certificate preserves cuts of values less than $k$ exactly, but cuts of a higher value are not preserved at all.

\begin{definition}
\label{definition:certificate}
Given an unweighted graph $G = (V, E)$, a \textit{sparse k-connectivity certificate} is a subgraph $H$ of $G$ with the properties:
\begin{enumerate}
    \item $H$ has at most $kn$ edges, and
    \item $H$ contains all edges crossing cuts of value $k$ or less.
\end{enumerate}
\end{definition}

Observe that the previous definition can be extended to weighted graphs if we replace an edge of weight $w$ with a set of $w$ unweighted edges with the same endpoints. Hence, the bound in size becomes a bound on the total weight of the remaining edges.  

There is one simple algorithm by Nagamochi and Ibaraki \cite{nagamochi1992linear, nagamochi1992computing} (that is enough for our purposes), which computes a sparse $k$-connectivity certificate of a graph $G$ as follows. Compute a spanning forest $F_1$ in $G$; then compute a spanning forest $F_2$ in $G - F_1$; and so on, continue computing spanning forests $F_i$ in $G - \cup_{j = 1}^{i} F_j$ 
until $F_k$ is computed. It is easy to see that the graph $H_k = \cup_{i = 1}^{k} F_i$ is $k$-connected and has $O(k n)$ edges. 

One can extend the algorithm onto the parallel setting by using e.g. the $O(m + n)$ work and $O(\log n)$ depth randomized algorithm of Halperin and Zwick \cite{HALPERIN20011} to find a spanning forest, from which the following bounds are obtained (see e.g. \cite[Sec. 2.3]{LopezMartinez1512083}). 

\begin{theorem}
\label{THEOREM:CONNECTIVITYCERTIFICATEPARALLEL}
Given an undirected weighted graph $G = (V, E)$, a $k$-connectivity certificate can be found \textit{w.h.p.} using $O(k(m + n))$ work and $O(k \log n)$ depth. 
\end{theorem}


\section{Approximating min-cut} \label{sec:approx_mincut}
We prove the following theorem:

\begin{theorem} \label{lem:approx-min-cut}
An $(1 \pm \eps)$-approximation of the minimum cut value of $G$ can be computed with work $O(m \log n + n \log^5 n)$ and depth $O(\log^3 n)$.
\end{theorem}

For simplicity of the exposition, we prove this theorem when $\eps = 1/3$. However, it is not hard to adapt the proof for any small constant $\eps$. Throughout this section, we switch between two representations of $G=(V,E)$: (i) as a weighted graph, and (ii) as an unweighted multigraph where we replace an edge $e =(u,v) \in E$ with weight $w(e)$ by $w(e)$ many unweighted copies of $e$ between the vertices $u$ and $v$. Whenever we use the term \textit{copies of an edge}, we denote the unweighted multigraph representation, and for referring to the original edges of the weighted graph $G$, we use the term \textit{weighted edges}. By \textit{sampling a weighted edge $e$ with probability $p$}, we mean sampling each of the $w(e)$ many unweighted copies of $e$ with probability $p$ independently. We use the following version of a concentration bound.

\begin{lemma}[Concentration bound] \label{lem:concentration}
Let $X_1, \cdots, X_k$ are iid boolean random variables and $X = \sum_i X_i$. Let us denote $\bbE[X] = \mu$. Then for any $\eps \in (0,1)$,
\begin{align*}
    \Pr[X \notin (1 \pm \eps) \mu] \leq 2 \cdot \exp(- \mu \cdot \eps^2/3).
\end{align*}
\end{lemma}


Consider the following family of graphs generated from $G$ by repeated sub-sampling of the unweighted copies of the edges of $G$.

\begin{definition}[Sampled hierarchy] Let $G = (V, E)$ is a weighted graph with total edge weight $W$, and let $k$ is an integer such that $2^k = W$. For any $i \in \{0, \cdots, k\}$, define $G_i$ to be a subgraph of $G_{i-1}$ where $G_i$ includes every unweighted edge of $G_{i-1}$ independently with probability $1/2$. Also, define $G_0 = G$ viewed as an unweighted multigraph. We denote the family $\{G_i\}_{i \in \{0,\cdots, k\}}$ to be the \textit{sampled hierarchy} of $G$.
\end{definition}

For $G$ with min-cut value $\lambda$, if we sample edges with probability $p$, then with probability $1 - o(1)$ we know that the resulting sampled graph will have min-cut value in the range $p\lambda(1 \pm \varepsilon)$ (given that $p \lambda = \Omega(\log n)$). We define the \textit{skeleton sampling probability} in the following way:

\begin{definition}
For a graph $G = (V, E)$ with min-cut value $\lambda$, define the skeleton sampling probability $p_s = 100 \log n/\lambda$.
\end{definition}

\begin{definition}[Skeleton layer]
Given a sampled hierarchy, we denote the skeleton layer as layer $s$ such that $2^{-s} = p_s$.
\end{definition}

Note that, at this point, we do not know that value of $\lambda$ of $G$, but we do know the following facts which follow from standard concentration argument (Lemma \ref{lem:concentration}, setting $\eps = 1/4$ for Claim \ref{clm:samp-hier-skeleton} and $\eps = 1/5$ and $1/3$ respectively for Claim \ref{clm:samp-hier-non-skeleton}).

\begin{claim} \label{clm:samp-hier-skeleton}
If we sample the edges of $G$ with probability $p_s$, then the value of the min-cut in $G_s$ is between $[75 \log n, 125 \log n]$ with high probability.
\end{claim}

\begin{claim}\label{clm:samp-hier-non-skeleton}
If we sample edges of $G$ with probability at least $2p_s$, then the value of the min-cut in the sampled graph is at least $160 \log n$. Similarly, if we sample with probability at most $p_s/2$, then the value of the min-cut in the sampled graph is at most $67 \log n$.
\end{claim}

A word of caution regarding the proof of Claim \ref{clm:samp-hier-non-skeleton}: For really small sampling probability, we may need to use the additive form of concentration bound which says the following: For any $\eps > 0$,
\begin{align*}
    \Pr[X > \mu + \eps] \leq \exp(- 2\eps^2/k),
\end{align*}
where we use the same notation as that in Lemma \ref{lem:concentration}. Hence, if we can compute the min-cut value in every $G_i$ in the sampled hierarchy, we can find out a $(1 \pm 1/4)$ approximation of the skeleton probability $p_s$ and, thereby, a $(1 \pm 1/3)$-approximation of $\lambda$. In the rest of this section, we elaborate on how to find these min-cut values.





\subsection{Computing min-cut in sampled hierarchy}

Of course, computing minimum cut na\"ively in each $G_i$ is not work efficient. Towards designing an efficient algorithm, we first define the \textit{critical layer} in the hierarchy for every weighted edge $e$.

\begin{definition}[Critical layer]
For a weighted edge $e \in E(G)$ with weight $w(e)$, define the critical layer $t_e$ in the sampled hierarchy w.r.t. the edge $e$ as the largest integer such that
\begin{align*}
\frac{w(e)}{2^{t_e}} \geq 500 \log n.
\end{align*}
\end{definition}

Given the notion of the \textit{critical layer}, we modify the sampled hierarchy in the following way:

\begin{definition}[Truncated hierarchy]
Given a graph $G = (V, E)$ and its corresponding sampled hierarchy $\{G_i\}_i$, we obtain the truncated hierarchy by removing all unweighted copies of any edge $e$ other than what is already present in $G_{t_e}$ from the layers $G_i, i < t_e$. We denote this hierarchy as $\{\Gtrunc_i\}_i$.
\end{definition}

The intuition behind \textit{truncating} the sampled hierarchy in this way is the following: In the graph $G_s$ of the sampled hierarchy (where $s$ is the skeleton layer), we know that the min-cut value is at most $125 \log n$ (Claim \ref{clm:samp-hier-skeleton}) and, hence, the number of unweighted copies of any weighted edge $e$ participating in the min-cut of $G_s$ is at most $125 \log n$. Hence it should not be a problem to remove any extra unweighted copies of $e$ from the hierarchy as they are useless as long as the min-cut of $G_s$ is concerned. We make this intuition concrete in the next section.

\subsubsection{Properties of the truncated hierarchy}

First, we bound the number of unweighted copies of any edge $e$ available in the truncated hierarchy. Note that, because of our definition of the critical layer, the expected number of copies of an edge $e$ in layer $t_e$ is $500 \log n$. The following claim follows from standard concentration argument (Lemma \ref{lem:concentration}, by setting $\eps = 1/5$).

\begin{claim} \label{clm:copies-in-trun-hier}
The number of unweighted copies of any edge $e$ in the critical layer $t_e$ of the truncated hierarchy is between $[400 \log n, 600 \log n]$ with high probability.
\end{claim}

Note that we need a guarantee that the min-cut in $\Gtrunc_s$ is \textit{well separated} from the min-cut values of $\Gtrunc_i$'s above and below the skeleton layer in order for us to find out where the skeleton layer is. The next three claims give us this guarantee.

\begin{claim}
For the skeleton layer $s$, the value of the min-cut in $\Gtrunc_s$ is $[75 \log n, 125 \log n]$ with high probability.
\end{claim}

\begin{proof}
This follows from the facts that (i) in the sampled hierarchy $\{G_i\}_i$, the value of the min-cut in $G_s$ is in the same range (Claim \ref{clm:samp-hier-skeleton}), and (ii) for every edge $e$ taking part in the min-cut, $t_e < s$. This is because, for any such edge $e$, the number of unweighted copies of $e$ in the min-cut of $G_s$ is at most $125 \log n$ w.h.p. whereas, in the critical layer $t_s$, the number of such copies is at least $400 \log n$ w.h.p.
\end{proof}

A similar argument also proves the following claim.
\begin{claim}
For layers $i > s$, the value of the min-cut in $\Gtrunc_s$ is at most $67 \log n$.
\end{claim}

For layers numbered less than $s$, we have to be careful because we may have removed edges in the truncated hierarchy. Nevertheless, we can prove the following claim which is enough for our purpose.

\begin{claim}
For layer $i < s$, the value of the min-cut in $\Gtrunc_i$ is at least $160 \log n$.
\end{claim}

\begin{proof}
We can do an exactly similar argument for the layer $s-1$ to conclude that the min-cut value in $\Gtrunc_{s-1}$ is at least $160 \log n$. The claim follows from the fact that the min-cut value cannot decrease as $\Gtrunc_{i} \subseteq \Gtrunc_{i-1}$ and the min-cut is a monotone function.
\end{proof}

\subsubsection{Obtaining the truncated hierarchy}


\begin{center}
  \centering
  \begin{minipage}[H]{0.8\textwidth}
\begin{algorithm}[H]
\caption{\textsc{Truncated (\& Exclusive) hierarchy computation}}\label{alg:hier-trunc}
\begin{algorithmic}[1]
\For{every edge $e$ in $G$}
    \State Compute the critical layer $t_e$.
\EndFor
\For{$i = 0$ to $k$}
    \For{all edge $e$ in $G$ with $t_e = i$}
        \State Sample binomially from $\cB(w(e), 2^{-i})$. Let the value of the random variable be $X$.
        \State Include $X$ many unweighted copies of $e$ in $\Gtrunc_i$.
    \EndFor
    \If{$i > 0$}
        \State Sample each edge of $\Gtrunc_{i-1}$ with probability $1/2$.
        \State Set $\hat G_{i-1} = \hat G_{i-1} \setminus \Gtrunc_i$.
    \EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
\end{minipage}
\end{center}

\begin{claim}
The truncated hierarchy can be computed (by Algorithm \ref{alg:hier-trunc}) with at most $O(m \log n)$ work and $O(\log n)$ depth.
\end{claim}

\begin{proof}
We assume that the random variables $X$ can be sampled from their corresponding binomial distribution in $O(\log n)$ work.\footnote{This follows from \cite{KachitvichyanukulS88} where the authors show that a random variable from $\cB(p, N)$ can be sampled in $O(Np + \log N)$ work and similar depth with high probability. For our purpose, this is $O(\log n)$ as we sample only at the critical layer.} For every edge $e$, we need to sample unweighted copies binomially in layer $t_e$. This requires $O(m \log n)$ amount of work across all layers of the truncated hierarchy. In addition, the total number of edges across the hierarchy is at most $O(m \log n)$. This is because, for each edge $e$ in $G$, at most $O(\log n)$ many unweighted copies are present across the hierarchy with high probability. Hence the total work is $O(m \log n)$. The depth of the computation is bounded by the depth of the hierarchy and the depth required to sample binomial random variables, which is $O(\log n)$.
\end{proof}


\subsubsection{Certificate hierarchy}

Even after obtaining the truncated hierarchy, finding min-cut in every $\Gtrunc_i$ can turn out to be expensive. We get around this problem by constructing $O(\log n)$-cut certificate for each $\Gtrunc_i$ and finding min-cut on those certificates. This reduces the work to $O(n\  \text{poly} \log n)$ as each such certificate has only $O(n\  \text{poly} \log n)$ many edges.

\begin{definition}[Exclusive hierarchy]
Given a truncated hierarchy $\{\Gtrunc_i\}_i$, we define the exclusive hierarchy $\{\hat G_i\}_i$ as follows: \begin{itemize}
    \item $\hat G_k = \Gtrunc_k$, and
    \item $\hat G_i = \Gtrunc_i \setminus \Gtrunc_{i+1}$,
\end{itemize}
where $G \setminus H$ for two graphs $G$ and $H$ on the same set of vertices includes edges that are \textit{exclusively} present in $G$ and are not in $H$.
\end{definition}

The exclusive hierarchy can be computed while computing the truncated hierarchy at no extra cost (See Algorithm \ref{alg:hier-trunc}). For certificate construction, the main idea is to come up with certificate $H_i$ for each $\hat G_i$ and use $\bigcup_{\geq i} H_i$ as a certificate for $\Gtrunc_i$. The following algorithm does exactly that with strict budgeting on the number of times a weighted edge $e$ participates in the certificate computation.

\begin{center}
  \centering
  \begin{minipage}[H]{0.8\textwidth}
\begin{algorithm}[H]
\caption{\textsc{Certificate hierarchy computation}}\label{alg:hier-cert}
\begin{algorithmic}[1]

\For{every weighted edge $e$}
    \State Initialize $\cnt_e$ to $400 \log n$.
\EndFor
\For{$i = k$ to $0$}
    \State Initialize $\fcnt = 0$ and $H_i = \emptyset$.
    \While{$\fcnt \leq 200 \log n$ or $\hat G_i \neq \emptyset$}
        \State Remove from $\hat G_i$ all copies of any edge $e$ such that $\cnt_e = 0$.
        \State Find a spanning forest $F$ of $\hat G_i$.
        \State For every edge $e$ in $\hat G_i$, set $\cnt_e = \cnt_e -1$.
        \State Set $\hat G_i = \hat G_i\setminus F$, $H_i = H_i \cup F$.
    \EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}
\end{minipage}
\end{center}

Algorithm \ref{alg:hier-cert} finds cut-certificates starting from $\hat G_k$ and moving upward in the exclusive hierarchy. In each iteration, it finds at most $200 \log n$ many spanning forests which are counted by the variable $\fcnt$. Note that, for any weighted edge $e$, the associated value $\cnt_e$ decreases in each spanning forest $F$ computation irrespective of whether any copy of $e$ is included in $F$ or not. The only way to stop the decrement of $\cnt_e$ in any iteration $i$ is to include all unweighted copies of $e$ present in $\hat G_i$ in the certificate $H_i$. This makes sure that each edge $e$ participates (and is not necessarily included) in at most $\cnt_e$ many spanning forest computations.


\begin{claim}
For any $i$, $\bigcup_{\geq i} H_i$ is a $200 \log n$-cut-certificate for $G_i$.
\end{claim}

\begin{proof}
Consider any $i$ and let $C$ be a cut of value at most $200 \log n$ in $G_i$. We need to show that this cut is maintained in $\bigcup_{\geq i} H_i$.

Consider any weighted edge $e \in C$ and its $\cnt_e$ at the $i$-th iteration. If $\cnt_e < 200 \log n$, then it means that $\bigcup_{> i}H_i$ already contains $200 \log n$ unweighted edges from $C$. This can be argued in the following way: Consider any spanning forest $F$ in $\bigcup_{> i}H_i$, computing which $\cnt_e$ decreased. Either $F$ includes an unweighted copy of $e$, or $F$ contains another unweighted edge crossing the cut $C$. In either case, $F$ contains at least 1 edge from $C$. Hence, each decrement of $\cnt_e$ corresponds to one unweighted edge crossing $C$ included in $\bigcup_{> i}H_i$.

If, on the other hand, $\cnt_e \geq 200 \log n$, then this edge is going to take part in all $200 \log n$ spanning forest computations in the $i$-th iteration. Hence $H_i$ will contain $200 \log n$ edges from $C$.
\end{proof}

We next compute the work and depth requirement for computing the certificate hierarchy.

\begin{claim}
Given the hierarchy $\hat G_i$, the certificates $\{H_i\}_i$ can be computed in work $O(m \log n)$ and depth $O(\log^3 n)$ with high probability.
\end{claim}

\begin{proof}
By the design of the algorithm, each edge takes part in at most $400 \log n$ spanning forest computation. Hence the total work is bounded by $400 \log n \times m = O(m \log n)$.

Calculating the depth is straight-forward. Note that there are $O(\log n)$ many layers in the certificate hierarchy, each amounting to $O(\log n)$ many spanning forest computation. We know that the depth required for computing a spanning forest is $o(\log n)$ \cite{HALPERIN20011}.
\end{proof}


\subsubsection{Computing min-cut on cut certificates}

\begin{claim}
The total work needed to compute min-cut on $\bigcup_{\geq i}H_i$ for all $i$ is at most $O(n \log^5 n)$ and the depth required is $O(\log^3 n)$.
\end{claim}

\begin{proof}
First note that the number of edges in $\bigcup_{\geq i}H_i$ for any $i$ is $O(n \text{poly} \log n)$. We can run either run the the algorithm designed by \cite{10.1145/3210377.3210393} or the algorithm designed in Section \ref{section.parallelMinimumCuts} to obtain the requires work and depth. For the approximation of min-cut (which is required in both of these two algorithms), we can use the expected min-cut value in $G_i$. If we use the algorithm in Section \ref{section.parallelMinimumCuts} then, to compute $O(\log n)$ many min-cuts---one for each $\bigcup_{\geq i}H_i$---the work required is $O(n \log^5 n)$ and the depth required is $O(\log^3 n)$ as we compute the $O(\log n)$ instances of min-cut parallelly. Using the algorithm of \cite{10.1145/3210377.3210393} gives worse dependence of $\text{poly} \log n$ in terms of work, but the depth remains $O(\log^3 n)$.
\end{proof}


\section{Exact Min-Cut} \label{section.parallelMinimumCuts}
%\section{Finding a Minimum 2-respecting Cut with optimal work and low depth}
In this section, we present our \textit{exact} parallel minimum cut algorithm. Following Karger's framework, the outline of the solution consists of (1) finding a tree packing and (2) for each tree in the packing, find the corresponding 2-respecting min-cut. The tree computations in part (2) of the algorithm are independent of each other, hence they can be safely executed in parallel.

Let $W_{pack}(m, n)$ and $D_{pack}(m, n)$ be the \textit{work} and \textit{depth} needed to find an appropriate packing of $O(\log n)$ trees, and let $W_{rsp}(m, n)$ and $D_{rsp}(m, n)$ be the work and depth required to find a minimum 2-respecting cut of a spanning tree. The \textit{work} and \textit{depth} bounds of a parallel min-cut algorithm can be expressed as:
\begin{align} 
W_{cut}(m, n) & = O( W_{pack}(m, n) + W_{rsp}(m, n)\log n), \label{eq:older_brother} \\
D_{cut}(m, n) & = O(D_{pack}(m, n) + D_{rsp}(m, n)). \label{eq:younger_brother}
\end{align}

In the following, we give parallel algorithms for both the tree-packing and 2-respecting steps. For the former, we consider our improved approximation algorithm of Section \ref{sec:approx_mincut} in the context of Karger's original packing procedure \cite{Kar00}. And for the latter, we rely on Mukhopadhyay and Nanongkai's minimum 2-respecting cut algorithm as described in \cite{gawrychowski2020note}. Put together via equations \eqref{eq:older_brother} and \eqref{eq:younger_brother}, our parallel algorithms imply the following overall bounds. 

\begin{theorem} \label{thm:exactMinCut}
The minimum cut in weighted graph can be computed w.h.p. using $W_{cut}(m, n) = O(m \log^2 n + n \log^5 n)$ work and $D_{cut}(m, n) = O(\log^3 n)$ depth.
\end{theorem}

%(In Section \ref{subsec:workOptimalDenseGraphs} we show how to improve this bound for non-sparse graphs.)
In the following, we first describe how to achieve this for general (weighted) graphs (Sections \ref{section.parallel2Respecting} and \ref{section.parallelPacking}). For non-sparse input graphs, in Section \ref{subsec:workOptimalDenseGraphs} we show how to further improve the work bound to $O(m \log n + n^{1+\epsilon})$. 

\subsection{Parallel 2-Respecting Min-Cut} \label{section.parallel2Respecting}
We begin with the parallelization of Mukhopadhyay and Nanongkai's \textit{simplified} 2-respecting min-cut algorithm \cite{gawrychowski2020note}. The approach follows the same structure as the sequential algorithm, except that we replace key data structures and subroutines with new parallel constructs. Together, this gives 
%a work-optimal parallel algorithm with low depth. 
an algorithm that is work-optimal with respect to its sequential counterpart and has low depth. 
%In this section we show that the 2-respecting minimum cut algorithm of Mukhopadhyay and Nanongkai can be parallelized work-optimally with low-depth. For its simplicity and slightly improved complexity, we rely on the description of the algorithm by Gawrychowski, Mozes, and Weimann \cite{gawrychowski2020note}. More precisely, we obtain the following bounds. 

\begin{theorem} \label{thm:Parallel2Respecting}
Given a spanning tree $T$ of a graph $G$, the minimum cut that 2-respects $T$ can be found \textit{w.h.p.} using $O(m \log m + n \log^3 n)$ work and $O(\log^2 n)$ depth.
\end{theorem}

We now describe how to implement each step of MN's algorithm (recall schematic from Section \ref{section.Background.subsection.MNAlgorithm}) in parallel and obtain the claimed work and depth complexities. In the following, we call the query that asks for the value $cut(e, f)$ given tree edges $e$ and $f$ a \textit{cut query}.

%The approach follows the same structure as the sequential algorithm, except that we replace key data structures and subroutines with new parallel constructs. 

\subsubsection{Tree decomposition}
The algorithm begins by partitioning the tree $T$ into a collection of edge-disjoint paths $\mathcal{P}$ with the following property: 
% such that any root-to-leaf path intersects at most $O(\log n)$ paths in $\mathcal{P}$

\begin{property}[Path Partition] \label{property:Partition}
Any root-to-leaf path in $T$ intersects $O(\log n)$ paths in $\mathcal{P}$.
\end{property}

Geissmann and Gianinazzi give a parallel algorithm \cite{10.1145/3210377.3210393} to compute such decomposition (a so-called \textit{bough decomposition}) which we can use as a black-box in our algorithm. %It requires only $O(n \log n)$ work and $O(\log^2 n)$ depth.

\begin{lemma}[{\cite[Lemma 7]{10.1145/3210377.3210393}}] \label{lemma:geissmann}
A tree with $n$ vertices can be decomposed \textit{w.h.p}\footnote{This result is originally Las Vegas, but by an application of Markov's inequality, it can easily be converted into a Monte Carlo algorithm.} into a set of edge-disjoint paths $\mathcal{P}$ satisfying Property \ref{property:Partition} using $O(n \log n)$ work and $O(\log^2 n)$ depth. 
\end{lemma}

Next, we will need a data structure for the tree decomposition which, on a node query, provides the set of paths in $\mathcal{P}$ which intersect the root-to-leaf path ending at that node. For this we give the following lemma. 
\begin{lemma} \label{lemma:1.1.2.1}
Let $\mathcal{P}$ be a set of edge-disjoint paths obtained by bough decomposition of a tree $T$. Given a tree $T$ of $n$ nodes and root $r$, there is a data structure that can preprocess $T$ with $O(n \log n)$ work and $O(\log^2 n)$ depth, and supports the following operation using $O(\log n)$ work and depth:
\begin{itemize}
    \item \textit{\textbf{Root-paths($u$)}}: given a node $u$, return an array of $O(\log n)$ disjoint paths $\mathcal{P}' \subseteq \mathcal{P}$, %(obtained by the bough decomposition of $T$), 
    such that every path $p \in \mathcal{P}'$ belongs to the same path from the root of $T$ to node $u$. %root-to-leaf path in $T$ as $e$.
\end{itemize}
\end{lemma}
\begin{proof}
We first show how to construct the data structure, and then analyze the query operation. 

\paragraph{Preprocessing.} We start by computing in parallel the postorder numbering of vertices in $T$ via the Eulerian circuit technique \cite{10.5555/133889}. 
This produces at each node $u$ the value $post(u)$ containing its rank in a postorder traversal of $T$. Next, we decompose tree $T$ in boughs, or paths, as in Lemma \ref{lemma:geissmann}. This produces an array of arrays $A$, where the element $A[i]$ consists of the sequence of edges representing a bough in $T$, arbitrarily indexed by $i$. Let $e \in A[i]$, we create the value $bough(e) = i$ to let $e$ know which bough it belongs to. This can be done trivially in parallel for every edge and every bough. The final step in the preprocessing is to sort the edges $e = (u, p(u))$ in each bough array $A[i]$ with respect to $post(p(v))$ in descending order, such that edges at shallower levels in $T$ appear first in the array. Note that $A[i][0]$ will contain the edge closest to the root in bough array $i$. %Let $\hat{e}_i = A[i][0]$. 

\medskip\noindent
\paragraph{Root-paths($u$).}
%\paragraph{Root-paths($e$).} 
Given a node $u$, we can find the desired boughs simply by walking up the tree from $u$ towards the root $r$, and keeping track of the boughs seen. Let $e = (u, p(u))$, where $p(u)$ denotes the parent of $u$. From the quantities defined during the construction, this can be done efficiently as follows:
\begin{enumerate}
    \item Initialize $i = bough(e)$.
    \item Set $\hat{e} = A[i][0]$ and append $i$ to the result list $L$. \label{step:2}
    \item If $\hat{e}$ is distinct from the root $r$, repeat step \ref{step:2} with $i = bough(p(\hat{e}))$.
    \item Return $L$.
\end{enumerate}

\medskip\noindent
\paragraph{Analysis.} 
For preprocessing, the step with the highest cost is the tree decomposition of Theorem \ref{lemma:geissmann}, which uses $O(n \log n)$ work and $O(\log^2 n)$ depth. All other steps are within the same work and depth bounds. The query algorithm performs only $O(1)$ work for each bough it finds on the way up from edge $e$ to the root of the tree. From Theorem \ref{lemma:geissmann}, there can be at most $O(\log n)$ such paths, and the result follows. 
\end{proof}

After decomposing the tree, the edges $e, f \in T$ that minimize $cut(e, f)$ can be distributed within the same path $p \in \mathcal{P}$, or in two distinct paths $p, q \in \mathcal{P}$. We now explain how to solve both cases efficiently in parallel. 

\subsubsection{Two edges in a single path} \label{subsection:SinglePath}
Let $p$ be a path in $\mathcal{P}$ of length $\ell$, and let $M_p$ be the $(\ell - 1) \times (\ell - 1)$ matrix defined by $M_p[i, j] = cut(e_i, e_j)$ with $e_i$ and $e_j$ the $i$-th and $j$-th edges of $p$. One key contribution of Mukhopadhyay and Nanongkai is in observing that the matrix $M_p$ is a \textit{Partial Monge} matrix. That is, for any $i \neq j$, it holds that $M_p[i, j] - M_p[i, j + 1] \geq M_p[i + 1, j] - M_p[i + 1, j + 1]$. To find the minimum entry in the matrix, MN give a divide-and-conquer algorithm that requires the computation of only $O(\ell \log^2 \ell)$ many cut queries. This algorithm can be shown to have a simple parallel implementation with optimal $O(\ell \log^2 \ell \cdot w_c(m))$ work and $O(d_c(m) \cdot \log \ell + \log^2 \ell)$ depth, where $w_c(m)$ and $d_c(m)$ are the work and depth required to compute a single cut query (see \cite{LopezMartinez1512083} for details). 

We can use instead an algorithm by Awarwall \textit{et al.} \cite[Thm. 2.3]{10.1145/97444.97693} that requires inspecting only $O(\ell \log \ell)$ many entries of a Partial Monge matrix using $O(\log \ell)$ depth. In Lemma \ref{lemma:dataStructureBinary} below, we show that a single cut query can be computed with optimal $w_c(m) = O(\log^2 n)$ work and $d_c(m) = O(\log n)$ depth. Thus, we can find the minimum cut determined by two edges of $p$ with $O(\ell \log^2 \ell \cdot \log^2 n)$ work and $O(\log \ell \cdot \log n)$ depth. Since paths in $\mathcal{P}$ are edge-disjoint, doing this for every path $p \in \mathcal{P}$ in parallel telescopes to the following bounds. %$O(n \log^3 n)$ total work and $O(\log^2 n)$ depth. 
%Thus, we can find the minimum 2-respecting cut restricted to single paths with total $O(n \log^3 n)$ work and $O(\log^2 n)$ depth. 

\begin{lemma} \label{lemma:parallelSinglePath}
Finding the minimum 2-respecting cut among all paths $p \in \mathcal{P}$ can be done in parallel with $O(n \log^3 n)$ work and $O(\log^2 n)$ depth.
%There is a parallel algorithm that finds the minimum 2-respecting cut among all paths $p \in \mathcal{P}$ using $O(n \log^3 n)$ work and $O(\log^2 n)$ depth. 
\end{lemma}

% \begin{lemma}[{\cite{LopezMartinez1512083}}]
% Let $G = (V, E)$ be a weighted graph, $T$ a spanning tree of $G$, and $p \in T$ a path of length $\ell$. There is a parallel algorithm that finds the minimum 2-respecting cut of $T$ in $G$ using $O(\ell \log^2 \ell \cdot w_c(m))$ work and $O(d_c(m) \cdot \log \ell + \log^2 \ell)$ depth, where $w_c(m)$ and $d_c(m)$ are the work and depth required to compute a single cut query. 
% \end{lemma}



\subsubsection{Two edges in distinct paths}
Now we look at the case when the tree edges $e, f \in T$ that minimize $cut(e, f)$ belong to different paths $p, q \in \mathcal{P}$ of combined length $\ell$. 

First observe that collapsing tree edges $e' \not\in p \cup q$ produces a residual graph with $p \cup q$ as its spanning tree, without changing the cut values determined by one edge being in $p$ and another in $q$. We could then run a similar algorithm to the previous section and find the smallest 2-respecting cut which respects one edge in $p$ and another in $q$. Doing this for every possible path-pair in $\mathcal{P}$ effectively serves to find the tree edges $e$ and $f$ that minimize $cut(e, f)$---but is not efficient, as the number of possible path-pairs is $O(n^2)$. Mukhopadhyay and Nanongkai solve this by showing that one must only inspect a small subset of \textit{interested path pairs}. (See Figure \ref{fig:crossAndDownInterest} for an illustration of the notion of \textit{interest}.)

\begin{figure}
    \centering
    \begin{tikzpicture}
    
    % Tree
    \node[draw, circle, inner sep=0pt,minimum size=1em, thick] (r0) at (0, 0.25) {$r$};
    
    % Left upper tree
    \coordinate (r01) at (-1, -0.25) {}; % root
    \node[draw, fill=black,, circle, inner sep=1.5pt] (s01) at (-1.5, -0.75) {}; % left
    \coordinate (s11) at (-0.5, -0.75) {}; % right
    
    \path[draw, thick] (r01)--(s01);
    \path[draw, thick] (s01)--(s11);
    \path[draw, thick] (s11)--(r01);
    
    % Left lower tree
    \node[draw, fill=black,, circle, inner sep=1.5pt] (r02) at (-2, -1.5) {}; % root
    \coordinate (s02) at (-2.75, -2.5) {}; % left
    \coordinate (s12) at (-1.25, -2.5) {}; % right
    
    \path[draw, thick] (r02)--(s02);
    \path[draw, thick] (s02)--(s12);
    \path[draw, thick] (s12)--(r02);
    
     % Right upper tree
    \node[draw, fill=black,, circle, inner sep=1.5pt] (rr01) at (1, -0.25) {}; % root
    \coordinate (rs11) at (0.5, -0.75) {}; % left
    \node[draw, fill=black,, circle, inner sep=1.5pt] (rs01) at (1.5, -0.75) {}; % right
    
    \path[draw, thick] (rr01)--(rs01);
    \path[draw, thick] (rs01)--(rs11);
    \path[draw, thick] (rs11)--(rr01);
    
    % Right lower tree
    \node[draw, fill=black,, circle, inner sep=1.5pt] (rr02) at (2, -1.5) {}; % root
    \coordinate (rs02) at (2.75, -2.5) {}; % left
    \coordinate (rs12) at (1.25, -2.5) {}; % right
    
    \path[draw, thick] (rr02)--(rs02);
    \path[draw, thick] (rs02)--(rs12);
    \path[draw, thick] (rs12)--(rr02);
    
    % Edges
    \draw[thick] (s01) -- node[left] {$e$} (r02);
    \draw[thick] (rs01) -- node[right] {$f$} (rr02);
    \draw[thick] (r0) -- (r01);
    \draw[thick] (r0) -- node[above] {$e'$} (rr01);
    \draw[thick, dashed] (-1.625, -2.0) -- (1.625, -2.0);
    \draw[thick, dashed] (-1.45, -2.25) -- (1.45, -2.25);
    \draw[thick, dashed] (-1.8, -1.8) -- (1.8, -1.8);
    
    \draw[thick, dashed] (-0.75, -0.5) -- (0.75, -0.5);
    %\draw[] (-1.8, -1.8) -- (1.8, -1.8);
    
    % up edges left
    \draw[thick, dashed] (-2.375, -2.0) arc(-135:-300:1cm);
    \draw[thick, dashed] (-2.5, -2.20) arc(-135:-300:1.2cm);
    %\draw[] (-2.25, -1.80) arc(-135:-300:0.8cm);
    %\draw[] (-2.375, -2.0) to [bend left=90] (-1.25, -.5);
    %\draw[] (-2.55, -2.25) to [bend left=90] (-1.10, -0.35);
    
    % up edges right
    \draw[thick, dashed] (2.375, -2.0) arc(-45:120:1cm);
    \draw[thick, dashed] (2.5, -2.20) arc(-45:120:1.2cm);
    %\draw[] (2.25, -1.80) arc(-45:120:0.8cm);
    
    \end{tikzpicture}
    \caption{Example graph and spanning tree illustrating the concept of interest. Tree-edges are represented by solid edges, and non-tree edges are represented by dashed lines. The graph is unweighted and the tree is rooted at $r$. Observe that edge $e$ is cross-interested in $f$, $f$ is cross-interested in $e$, and $e'$ is down-interested in $f$.}
    \label{fig:crossAndDownInterest}
\end{figure}

\begin{definition}[Interest \cite{mukhopadhyay2019weighted, gawrychowski2020note}] \label{definition:interest}
Let $T_e$ denote the sub-tree of $T$ rooted at the lower endpoint (furthest from the root) of $e$, and let $w(T_e, T_f)$ be the total weight of edges between $T_e$ and $T_f$. In particular, we denote $w(T_e) = w(T_e, T \setminus T_e)$. Then:
\begin{enumerate}
    \item an edge $e \in T$ is said to be \textit{cross-interested} in an edge $f \not\in T \setminus T_e$ if $w(T_e) < 2w(T_e, T_f)$, 
    \item an edge $e \in T$ is said to be \textit{down-interested} in an edge $f \in T_e$ if $w(T_e) < 2w(T_f, T \setminus T_e)$,
    \item an edge $e \in T$ is said to be interested in a path $p \in \mathcal{P}$ if it is cross-interested or down-interested in some edge of $p$,
    \item two paths $p, q \in \mathcal{P}$ are said to be an \textit{interested path pair} if $p$ has an edge interested in $q$ and vice versa.
\end{enumerate}
\end{definition}

\begin{claim}[\cite{mukhopadhyay2019weighted, gawrychowski2020note}] \label{claim:pathRootToNode}
For any tree edge $e$:
\begin{enumerate}
    \item all the edges that $e$ is cross-interested in consist of a single path in $T$ going down from the root of $T$ up to some node $c_e$.
    \item all the edges that $e$ is down-interested in consist of a single path in $T$ going down from $e$ up to some node $d_e$.
\end{enumerate}
\end{claim}

Observe that, from Property \ref{property:Partition} and Claim \ref{claim:pathRootToNode}, an edge is interested in at most $O(\log n)$ paths from $\mathcal{P}$. Hence, the total number of interested path pairs is $O(n \log n)$. Finding such a subset of paths is one of the main insights of Gawrichowski, Mozes, and Wiemann's simplification \cite{gawrychowski2020note} of the original MN's algorithm. They do this through a \textit{centroid decomposition} of the tree $T$ which, for every edge $e \in T$, serves to guide the search for the nodes $c_e$ and $d_e$ that delimit the paths on which an edge can be interested in. Once these nodes have been identified, using the data structure of Lemma \ref{lemma:1.1.2.1} one may find all interested edge pairs. 

Before looking at the parallel implementation of such procedure, however,
we give the following lemma 
%in the following lemma we show how 
to efficiently determine in parallel whether an edge $e$ is interested in another edge $f$. This also serves to %show how one can 
compute the cut query $cut(e, f)$ with optimal work and low depth. 

\begin{lemma} \label{lemma:dataStructureBinary}
Given a weighted graph $G = (V, E)$ and a spanning tree $T$ of $G$, there exists a data structure that can be preprocessed in parallel with $O(m \log m)$ work and $O(\log n)$ depth, and given two edges $e$ and $f$, it can report the following with $O(\log^2 n)$ work and $O(\log n)$ depth: (1) the value $cut(e, f)$, (2) whether $e$ is cross-interested in $f$, and (3) whether $e$ is down-interested in $f$. 
\end{lemma}
\begin{proof}
Proof in the appendix.
\end{proof}

\paragraph{Finding interested path pairs}
We now look at the parallel procedure to find the subset of interested path pairs. To begin, we look at the definition of a centroid decomposition and its parallel construction. 

\begin{definition}[Centroid]
Given a tree $T$, a node $v \in T$ is a \textit{centroid} if every connected component of $T \setminus \{v\}$ consists of at most $|T|/2$ nodes. 
\end{definition}

Without loss of generality, we can assume that the input tree $T$ is a binary tree. Otherwise, simply replace a node of degree $d$ with a binary tree of size $O(d)$, where internal edges have weight $\infty$ and edges incident to leaves preserve their original weight. It is easy to see that this can be done in parallel with $O(d)$ work and $O(\log d)$ depth by constructing each tree in a bottom-up fashion. 

\begin{definition}[Centroid decomposition]
Given a tree $T$, its \textit{centroid decomposition} consists of another tree $T'$ defined recursively as follows: 
\begin{itemize}
    \item the root of $T'$ is a centroid of $T$.
    \item children of the root of $T'$ are centroids of the sub-trees that result from removing the centroid of $T$. 
\end{itemize}
\end{definition}

%Since we assumed that $T$ is binary, there can be at most $O(\log n)$ steps in the recursion. 

\begin{lemma}
The centroid decomposition of a tree $T$ of size $n$ can be computed in parallel with optimal $O(n \log n)$ work and $O(\log n)$ depth.
\end{lemma}
\begin{proof}
% To find a centroid, the classical sequential solution is to (i) select an arbitrary node $v$ of $T$, (ii) compute subtree sizes foe each node $u \in T$ and (iii) check if node $v$ is a centroid of $T$. If so, then return $v$. If it is not, then repeat (iii) on the adjacent node $w$ whose subtree $T_w$ is of greatest size; i.e., $|T_w| > |T|/2$. 

% In parallel, we can find a centroid of a tree similar to the sequential case. Steps (i) and (ii) can be done efficiently in parallel with $O(n)$ work and $O(\log n)$ depth
First, we compute sub-tree sizes for each node $u \in T$. In parallel, this can be done with optimal $O(n)$ work and $O(\log n)$ depth by the application of the \textit{Eulerian circuit} technique from parallel graph algorithms \cite{10.5555/133889}. To find a centroid, we can simply test each node for the centroid property independently in parallel. This can be done with $O(n)$ work and $O(1)$ depth, as each node reads the sub-tree sizes of at most 3 other nodes. Next, we aggregate the results in a bottom-up fashion and return any of the identified centroids. This requires $O(n)$ work and $O(\log n)$ depth. From recursing $O(\log n)$ times (in parallel) and at each level of the recursion performing only $O(n)$ work and $O(\log n)$ depth, the overall parallel complexity follows. 
\end{proof}

As mentioned previously, to find the set of interested path pairs, we identify the nodes $c_e$ and $d_e$ for every edge $e \in T$. 

\begin{claim}
For every edge $e \in T$, we can identify the nodes $c_e$ and $d_e$ in parallel using $O(n \log^3 n)$ work and $O(\log^2 n)$ depth.
\end{claim}
\begin{proof}
Let $e'$ be a tree edge, and let $c$ be the centroid node of $T$, we obtain the node $c_e$ (resp. $d_e$) as follows: (1) for the (up to) three edges $e_1$, $e_2$ and $e_3$ incident to $c$, check if edge $e'$ is cross-interested (resp. down-interested) in each of them, (2) if $e'$ is interested in $e_i$, recurse on the subtree $T_{e_i}$, (3) else, return the current centroid node as $c_{e'}$ (resp. $d_{e'}$). The correctness of the algorithm rests on %the fact that, if $e$ is interested in the edge $f = (par(c_e), c_e)$, then it is interested in all the edges from $c_e$ to the root of $T$. 
the correctness of Claim \ref{claim:pathRootToNode}.

Using Lemma \ref{lemma:dataStructureBinary} we can check with $O(\log^2 n)$ work and $O(\log n)$ depth whether edge $e$ is interested in $e_1$, $e_2$ and $e_3$. And since the depth of the recursion is $O(\log n)$ (as we assume $T$ is binary), the procedure takes $O(\log^3 n)$ work and $O(\log^2 n)$ depth for a single edge $e$. Since we may use execute this algorithm independently in parallel for each edge, the main claim follows from multiplying the work by the number of edges $n$. 
\end{proof}

\paragraph{Checking interested path pairs.}
For each pair of interested paths $p, q \in \mathcal{P}$, we want to determine the list $r = \{e_1, \ldots, e_p\}$ of edges of $p$ that are interested in $q$ and the list $s = \{f_1, \ldots, f_p\}$ of edges from $q$ that are interested in $p$. %Collapsing all tree edges $e' \not\in L_p \cup L_q$ produces a residual graph with the path defined by $L_p \cup L_q$ as its spanning tree, which we have seen gives raise to some nice properties that we can exploit. 
Observe that since the number of interested path pairs is only $O(n \log n)$, the total length of these lists is also $O(n \log n)$. 

\begin{definition}[Interest tuples]
For a tree edge $e \in p$ such that $p \in \mathcal{P}$, given its terminal nodes $c_e$ and $d_e$, we define its \textit{interest tuples} $\mathcal{T}_e$ as the list of tuples of the form $(p, q, e)$ such that $q \in \mathcal{P}$ belongs to the unique path from $c_e$ to the root of $T$, and likewise for $d_e$. 
\end{definition}

\begin{claim} \label{claim:Tuples1}
The list of interest tuples $\Gamma = \bigcup_{e \in T} \mathcal{T}_e$ can be computed in parallel using $O(n \log n)$ work and $O(\log n)$ depth.
\end{claim}
\begin{proof}
%\TODO{Complete proof.}
For an edge $e \in T$, given the nodes $c_e$ and $d_e$ we can identify the set of paths $\mathcal{P}_e$ from $\mathcal{P}$ that $e$ is cross- and down-interested in simply from issuing two \textbf{Root-paths} queries to the data structure of Lemma \ref{lemma:1.1.2.1} with nodes $c_e$ and $d_e$. This requires $O(\log n)$ work and depth per edge. From issuing all $O(n)$ queries in parallel, we get the claimed complexity bounds. Preparing the interest tuple $(p, q, e)$ on each iteration accounts for only $O(1)$ time. 
\end{proof}

\begin{lemma} \label{lemma:1.1.6}
Given a sequence $\Gamma$ of $n$ tuples of the form $(A, B, x)$, with 
$A$ and $B$ drawn from a totally ordered set $\mathcal{S}$, there exists a parallel algorithm that generates a sequence $F$ of tuples of the form $(A, \{x_1, \ldots, x_a\}, B, \{y_1, \ldots, y_b\})$ with $O(n \log n)$ work and $O(\log n)$ depth; such that for each $x_i$ the tuple $(A, B, x_i)$ appears in $\Gamma$, and for each $y_i$ the tuple $(B, A, y_i)$ appears in $\Gamma$. 
\end{lemma}
\begin{proof}
See Lemma 4.16 in \cite{LopezMartinez1512083}. 
% In parallel, for each tuple $\gamma_i = (A_i, B_i, x_i) \in \Gamma$ the idea is to first compare $A_i$ and $B_i$ and swap them if $B_i < A_i$, marking tuple $\gamma_i$ if its entries were swapped. Then we sort $\Gamma$ by lexicographic order to group together all tuples with the same first and second elements. Any duplicated tuples are removed. We can easily identify contiguous subsequences of tuples $\Gamma_{AB} \in \Gamma$ such that $A_i = A$ and $B_i = B$ for all $\gamma_i \in \Gamma_{AB}$. Now, in parallel, for each such subsequence, we split $\Gamma_{AB}$ into marked tuples $\Gamma_{AB}'$ and unmarked tuples $\Gamma_{AB}''$, and construct the new tuple $f_{AB} = (A, \{x_i\}, B, \{y_j\}) \mid (A, B, x_i) \in \Gamma_{AB}'' \land (A, B, y_j) \in \Gamma_{AB}'$. Finally we just append such tuples together in parallel into a new sequence $F$ and return the result.
%
% It is clear from the definition of tuples $F$ that the described procedure produces the correct result. As for the parallel cost, the most expensive step is the lexicographical sorting of tuples, which uses $O(n \log n)$ work and $O(\log n)$ depth by the bounds on parallel sorting by R. Cole \cite{10.1137/0217049}. Duplicated tuples can be easily removed within the same bounds \cite[Thm. 2.18]{LopezMartinez1512083}. Identifying equal contiguous subsequences of tuples (up to their second entry) can be done with linear work and logarithmic depth from a combination of the \textit{divide-and-conquer} and \textit{binary-tree} design strategies. The marked and unmarked tuple splitting, as well as the new tuples construction, can be done within the same \textit{work-depth} bounds using \textit{prefix-sums} \cite{10.5555/133889}. Therefore, the claim follows.% Observe that all steps can be performed without concurrent reads or writes. 
\end{proof}

The application of Claim \ref{claim:Tuples1} together with Lemma \ref{lemma:1.1.6} serves two purposes: (1) to identify the set of interested pairs, and (2) for each such pair $p, q \in \mathcal{P}$, to identify the lists $r$ and $s$ of edges that actively participate in the interest relation. Once we have a sequence of tuples $F$ as in Lemma \ref{lemma:1.1.6}, and thus, the set of all interested path pairs, we can proceed to find the minimum 2-respecting cut as follows. 

Consider any tuple $(p, r, q, s) \in F$. Let $|r|$ and $|s|$ denote the sizes of lists $r$ and $s$, respectively, and let $\ell$ be the combined size of the two. Collapsing tree edges $e' \not\in r \cup s$ produces a residual graph with $r \cup s$ as its spanning tree, without changing the cut values determined by one edge being in $p'$ and another in $q'$. Let $M_{pq}$ be the $(|r| - 1) \times (|s| - 1)$ matrix defined by $M_{rs}[i, j] = cut(e_i, e_j)$ where $e_i$ is the $i$-th edge of $r$ and $e_j$ the $j$-th edge of $s$. Similar to single-path case, Mukhopadhyay and Nanongkai observe that the matrix $M_{rs}$ is a Monge matrix (see e.g., \cite[Claim 3.5]{mukhopadhyay2019weighted} and \cite[Lemma 2]{gawrychowski2020note} for details). That is, it satisfies that $M_{rs}[i, j] - M_{rs}[i, j + 1] \geq M_{rs}[i + 1, j] - M_{rs}[i + 1, j + 1]$ for any $i, j$ (in contrast with $i \neq j$ for single paths). 

A simplified variant of the divide-and-conquer algorithm discussed in Section \ref{subsection:SinglePath} can be easily parallelized with optimal $O(\ell \log \ell \cdot \log^2 n)$ work and $O(\log \ell \cdot \log n)$ \cite{LopezMartinez1512083}. However, we can opt for an algorithm with better work and use the parallel (and randomized) algorithm of Raman and Vishkin \cite{10.5555/314464.314661} that inspects only a linear $O(\ell)$ number of entries of a Monge matrix with $O(\log \ell)$ depth. Now observe that each tuple $f \in F$ may be processed independently in parallel. Using Lemma \ref{lemma:dataStructureBinary} for each entry inspection, and the fact that the $\sum \ell$ over all interested pairs is $O(n \log n)$, we obtain the following parallel bounds.      

\begin{lemma} \label{lemma:parallelInterestedPaths}
Finding the minimum 2-respecting cut among all interested path pairs $p, q \in \mathcal{P}$ can be done in parallel with $O(n \log^3 n)$ work and $O(\log^2 n)$ depth.
%There is a parallel algorithm that finds the minimum 2-respecting cut among all paths $p \in \mathcal{P}$ using $O(n \log^3 n)$ work and $O(\log^2 n)$ depth. 
\end{lemma}

Putting together the results of Lemmas \ref{lemma:1.1.2.1}, \ref{lemma:parallelSinglePath}, \ref{lemma:dataStructureBinary} and \ref{lemma:parallelInterestedPaths} we obtain the parallel bounds stated in Theorem \ref{thm:Parallel2Respecting}. 

%\section{Finding good trees in parallel with less work and low depth}
\subsection{Parallel Tree Packing} \label{section.parallelPacking}
Let $G = (V, E)$ be an undirected weighted graph. Karger already showed \cite[Corollary 4.2]{Kar00} that computing an appropriate tree packing in parallel can be done with $O(m \log^3 n + n \log^4 n)$ work and $O(\log^3 n)$ depth\footnote{In Karger's paper this result is stated in terms of parallel time and the number of processors that realize it.}. Using this result as a black box in Karger's tree packing framework, along with Theorem \ref{thm:Parallel2Respecting}, one can easily derive a randomized parallel min-cut algorithm that requires only $O(m \log^3 n + n \log^4 n)$ work and $O(\log^3 n)$ depth. This is already an improvement compared to Geissmann and Gianinazzi's $O(m \log^4 n)$ work algorithm when graphs are at least near-linear in size (that is, $m = \Omega(n \log n)$). However, the algorithm is not work-optimal in any setting. 

%To obtain a greedy tree packing with better work complexity and hence, a better min-cut algorithm, we follow Karger's general framework. It consists of two phases: (1) \textit{sparsifier} phase, where we compute a skeleton graph $H$ of our input graph containing fewer edges; and (2) \textit{packing} phase, where we find a set of size $O(\log n)$ (by weight) of appropriate spanning trees in $H$. 

%To achieve work optimality in non-sparse graphs, we show that a 

In this section we show that the work bound for packing an appropriate set of spanning trees can be improved in a $O(\log^2 n)$ factor. More precisely, we obtain the following: 

\begin{theorem} \label{theorem:1.2}
Given a weighted graph $G = (V, E)$, we can compute a packing $\mathcal{S}$ of $O(\log n)$ spanning trees (by weight) such that, \textit{w.h.p.} the minimum cut 2-respects at least one of the trees in $\mathcal{S}$, using $O(m \log n + n \log^5 n)$ work and $O(\log^3 n)$ depth. 
\end{theorem}

Plugging the bounds of Theorem \ref{theorem:1.2} and Theorem \ref{thm:Parallel2Respecting} into equations \eqref{eq:older_brother} and \eqref{eq:younger_brother} of Section \ref{section.parallelMinimumCuts}, we obtain the complexity claim of Theorem \ref{thm:exactMinCut}.  

%We have already stated (Section \ref{sec:prelims}) that the tree packing step of Karger's algorithm 
Recall that Karger's \cite{Kar00} tree packing step consists of two phases: (1) \textit{sparsifier} phase, where we compute a skeleton graph $H$ of our input graph containing fewer edges; and (2) \textit{packing} phase, where we find a set of size $O(\log n)$ (by weight) of appropriate spanning trees in $H$. %This latter phase is very easy to parallelize, as the only non-basic operation involved is a minimum spanning tree computation, 
The latter phase is a classical packing algorithm of Plotkin, Shmoys, and Tardos \cite{plotkin1995fast, thorup2000dynamic, neal1995randomized} and consists of a series of $O(\log^2 n)$ sequential minimum spanning tree (MST) computations. This algorithm can be easily parallelized with $O(n \log^3 n)$ work and $O(\log^3 n)$ depth from considering an appropriate MST parallel algorithm: e.g., Pettie and Ramachandran's \cite{pettie2002randomized} $O(n)$ optimal work and $O(\log n)$ depth (randomized) algorithm. This leaves the sparsifier phase as the sole bottleneck for constructing an appropriate tree packing with better work complexity. 

In the following, we assume that we have computed a constant factor underestimate $\tilde{\lambda}$ of the min-cut of $G$ via our approximation algorithm of Theorem \ref{lem:approx-min-cut}. Simply find a $(1 \pm 1/3)$-approximation $\lambda'$ of the min-cut and set $\tilde{\lambda} = \lambda' / 2$. This accounts for the additive $O(n \log^5 n)$ factor in the work bound of Theorem \ref{theorem:1.2}. %Otherwise, compute a $(1 \pm 1/3)$-approximation $\lambda'$ of the min-cut as in Theorem \ref{lem:approx-min-cut} and set $\tilde{\lambda} = \lambda' / 2$. This accounts for the additive $O(n \log^5 n)$ factor in the work bound of Theorem \ref{theorem:1.2}.

% To achieve this we follow Karger's approach consisting of two main phases: (1) \textit{sparsifier} phase, where we compute a skeleton graph $H$ of our input graph containing fewer edges, and (2) \textit{packing} phase, where we find a set of size $O(\log n)$ (by weight) of appropriate spanning trees in $H$. 

% Step 2 consists of a series of $O(\log^2 n)$ sequential minimum spanning tree (MST) computations, and can be easily parallelized with $O(n \log^3 n)$ work and $O(\log^3 n)$ depth from considering an appropriate MST parallel algorithm, e.g., Pettie and Ramachandran's \cite{pettie2002randomized} $O(n)$ optimal work and $O(\log n)$ depth (randomized) algorithm. The bottleneck is then to compute an appropriate sub-graph $H$ of $G$. 

% To achieve this, we use our approximation algorithm of Section \ref{sec:approx_mincut} to reduce the work required to construct a \textit{skeleton} graph $H$ of $G$ in parallel. Then, following Karger's framework, we can pack $O(\log n)$ many trees 


% Following Karger's approach, we can use this skeleton to find an appropriate set of spanning trees via an easy parallelization of the classical packing algorithm of Plotkin, Shmoys and Tardos \cite{plotkin1995fast, thorup2000dynamic, neal1995randomized}.

\subsubsection{Constructing Skeletons with Less Work}
Given a weighted graph $G = (V, E)$ with minimum cut $\lambda$, and an error parameter $\eps$, we are interested in finding a sparse subgraph $H = (V, E')$ on the same vertices that satisfies the following properties with high probability:

\begin{property} \label{property1}
$H$ has total weight $O(n \log n / \eps^2)$.
\end{property}
\begin{property} \label{property2}
The minimum cut in $H$ has value $\lambda' = O(\log n / \eps^2)$.
\end{property}
\begin{property} \label{property3}
the value of the minimum cut in $G$ corresponds (under the same vertex partition) to a $(1 \pm \eps)$ times minimum cut of $H$. 
\end{property}

% \begin{itemize}
%     \item \emph{Property 1:} $H$ has total weight $O(n \log n / \epsilon^2)$, 
%     \item \emph{Property 2:} the minimum cut in $H$ has value % within $(1 \pm \epsilon)$ times its expected value, of size 
%     $\lambda' = O(\log n / \epsilon^2)$, 
%     \item \emph{Property 3:} the value of the minimum cut in $G$ corresponds (under the same vertex partition) to a $(1 \pm \epsilon)$ times minimum cut of $H$. 
% \end{itemize}

In the sequential case, Karger constructs $H$ by (i) finding a sparse connectivity certificate $G'$ of $G$ with $O(n \log n)$ total weight, and then (ii) building the skeleton $H$ with bounded min-cut value $O(\log n)$. In parallel, however, this does not work as there is no parallel algorithm to construct a sparse connectivity certificate with complexity independent of the min-cut value $\lambda$. One way to remedy this parallel dependency on $\lambda$ is to first construct an appropriate skeleton of $G$ to reduce the effective minimum cut in the graph to $O(\log n)$, and then construct a sparse $k$-connectivity certificate with $k = O(\log n)$ to bound the total edge weight to $O(n \log n)$. 

%There is one challenge with this approach, however, and it is that the total weight $W$ of the input graph $G$ may be arbitrarily large. This means that sampling (naively) from the weight of $G$ takes work proportional to $W$. 
To make sampling efficient, we make the following simple observation (also appearing in \cite{bhardwaj_et_al:LIPIcs:2020:12259}).

\begin{observation} \label{observation:skeletonCap}
For a skeleton graph $H$ of $G$ satisfying Properties \ref{property2} and \ref{property3}, the weight of each edge in $H$ need not be greater than the maximum size of the minimum cut in $H$, thus $O(\log n / \eps^2)$.
\end{observation}
\begin{proof}
From Theorem \ref{theorem:samplingTheorem}, the minimum cut in $H$ will be at most $(1 + \eps)$ times its expected value $\hat{\lambda} = O(\log n / \eps^2)$ with high probability. Since edges with weight greater than $\hat{\lambda}$ never cross the minimum cut, capping their weight to a value greater than $\hat{\lambda}$ but still $O(\log n / \eps^2)$---e.g., $\ceil{c + \hat{\lambda}}$ for some constant $c \geq 2$---does not impact the minimum cut of $H$, and Properties \ref{property2} and \ref{property3} that only depend on such min-cut being approximately preserved, are still satisfied.
\end{proof}

Recall that we can build the weighted skeleton $G'$ of a graph $G$ by letting edge $e$ in $G'$ have weight drawn from the binomial distribution with probability $p$ and the number of trials weight $w(e)$ from $G$. Using \textit{inverse transform} sampling \cite{fishman1979sampling, fishman2013discrete} and Observation \ref{observation:skeletonCap}, we can avoid sampling values greater than the maximum size of the min-cut in $G'$, which is $O(\log n)$. Thus, the weight of each edge $e \in G'$ can be obtained using only $O(\log n)$ sequential work. From sampling independently in parallel for every $e \in G$, and then applying Theorem \ref{THEOREM:CONNECTIVITYCERTIFICATEPARALLEL} for the certificate construction, we obtain the following lemma.

% %Using an efficient sampling method 
% A weighted skeleton $G'$ of a graph $G$ can be built by letting edge $e$ in $G'$ have weight drawn from the binomial distribution with probability $p$ and the number of trials weight $w(e)$ from $G$. One sampling method that can be used in conjunction with Observation \ref{observation:skeletonCap} towards an efficient skeleton construction is the \textit{inverse transform} method. 

\begin{lemma}
\label{lemma:1.2.1}
Given a weighted graph $G = (V, E)$, an error parameter $\eps > 0$, and a constant underestimate of the min-cut $\tilde{\lambda}$, using $O(m \log n / \eps^2)$ work and $O(\log^2 n / \eps^2)$ depth, we can construct a sparse sub-graph graph $H = (V, E')$ satisfying properties \ref{property1}, \ref{property2} and \ref{property3}.
%satisfying the following properties with high probability:
% \begin{itemize}
%     \item \emph{Property 1:} $H$ has total weight $O(n \log n / \epsilon^2)$, 
%     \item \emph{Property 2:} the minimum cut in $H$ has value $O(\log n / \epsilon^2)$, and 
%     \item \emph{Property 3:} the value of the minimum cut in $G$ corresponds (under the same vertex partition) to a $(1 \pm \epsilon)$ times minimum cut of $H$. 
% \end{itemize}
\end{lemma}

The correctness follows from using an appropriate underestimate $\tilde{\lambda}$ of the min-cut which, by Theorem \ref{theorem:samplingTheorem}, produces a skeleton graph satisfying properties \ref{property2} and \ref{property3}. Property \ref{property1} is satisfied by the definition of sparse connectivity certificate. 

%\subsection{Improving work bound}

%\subsection{Proof of Theorem ?}

%\subsection{Proof of Theorem ?}
\subsection{Work-Optimality for Dense Graphs} \label{subsec:workOptimalDenseGraphs}
In this section we further improve the work bound of Theorem \ref{thm:exactMinCut} for non-sparse input graphs; that is, when $m = n^{1+\Omega(1)}$. %For this, we need only replace the parallel geometric data structure of Lemma \ref{lemma:dataStructureBinary} with the 2-dimensional data structure of Lemma \ref{lemma:2DimensionalEpsolinTree}. Before this, however, we design the following 1-dimensional structure.
We need the following 1- and 2-dimensional data structures:

\begin{lemma} \label{lemma:1DimensionalEpsolinTree}
For any $\epsilon > 0$, given a set $S$ of $m$ weighted points in $[n]$, there is a parallel data structure that preprocesses $S$ with $O(m/\epsilon)$ work and $O(\log n)$ depth, and reports the total weight of all points in any given interval $[x_1, x_2]$ in parallel with $O(n^\epsilon / \epsilon)$ work and $O(\log n)$ depth. 
\end{lemma}
\begin{proof}
%\TODO{Complete proof.} 
We first show how to construct the data structure, and then analyze the query operation. 
\paragraph{Preprocessing.} First we sort the points of $S$ in ascending order with $O(m)$ work and $O(\log n)$ depth using a parallel radix sort algorithm \cite{GuyEBlelloch}. Next, we construct a complete tree $C$ on $S$ with degree $n^\epsilon$, where the leaves store the points of $S$ in sorted order, and every inner node $u$ stores the tuple $(key(u), key(v))$ where $u$ and $v$ are, respectively, the leftmost and rightmost leaf nodes in the sub-tree rooted at $u$.
%The internal nodes of the tree can be constructed independently in parallel with $O(n)$ work and $O(1)$ depth.
The tree can be constructed in parallel in a bottom-up (or up-sweep) fashion starting at the leaves using $O(n)$ work and $O(1/\epsilon) < O(\log n)$ depth\footnote{This is true because the degree $n^\epsilon$ must be greater than or equal to 2 to be valid, hence $\epsilon > 1/\log n$ and $1/\epsilon \leq \log n$.}. 

%At a given level of the tree, each node $u$ can be created independently.  
Each internal node $u$ stores the value $W(u)$, consisting of the total weight of leaves in its sub-tree $C_u$. This can be computed in an up-sweep fashion with $O(n^\epsilon)$ work and $O(\epsilon \cdot \log n)$ depth. Hence, at each depth of the tree $C$, a total of $O(m)$ work and $O(\epsilon \cdot \log n)$ depth is done. And since there are a total of $O(1/\epsilon)$ levels in $C$, then the whole construction takes $O(m / \epsilon)$ work and $O(\log n)$ depth.  

\paragraph{Query.} For an internal node $u$, the idea is to inspect each of its $O(n^\epsilon)$ possible children independently in parallel and aggregate their weights in an up-sweep fashion. What we want is to identify the left $u_\ell$ and right $u_r$ children of $u$ whose leaves (the leaves on their corresponding sub-trees) are not entirely contained in the query interval $[x_1, x_2]$, and to sum the total weight contributed by each of the children in between. This can be done with $O(n^\epsilon)$ work---as node $u$ has up to $O(n^\epsilon)$ children---and $O(\epsilon \cdot \log n)$ depth. Now, each level must be processed sequentially, and the tree $C$ has $O(1/\epsilon)$ depth. Hence, the total query work is $O(n^\epsilon / \epsilon)$ and the depth is $O(\log n)$. 
\end{proof}

\begin{lemma} \label{lemma:2DimensionalEpsolinTree}
For any $\epsilon > 0$, given $m \geq n$ weighted points in the $[n] \times [n]$ grid, we can construct with work $O(m / \epsilon)$ and depth %$O(\log n / \epsilon)$ 
$O(\log^2 n)$ 
a data structure that reports the total weight of all points in any given rectangle $[x_1, x_2] \times [y_1, y_2]$ with $O(n^\epsilon/\epsilon^2)$ work and $O(\log n)$ depth. 
\end{lemma}
\begin{proof}
We show how to construct the data structure and then analyze the query operation.

\paragraph{Preprocessing.} Similar to the standard 2-dimensional \textit{range tree} data structure \cite{BENTLEY1979244}, we split our construction into two parts: (1) constructing a main, or first-level, $x$-coordinate tree $\mathscr{T}$ on $S$; and (2) at the second-level, constructing $y$-coordinate auxiliary array $A(u)$ and tree $\mathscr{T}_{aux}(u)$ on the leaves spanned by the sub-tree rooted at $u$, for each internal node $u \in \mathscr{T}$. 
\begin{enumerate}
    \item First level: We begin by sorting the points in $S$ in ascending order along their $x$-coordinates using a parallel radix sort algorithm \cite{GuyEBlelloch} with $O(m)$ work and $O(\log n)$ depth. Next, we construct the complete $O(n^\epsilon)$-degree tree $\mathscr{T}$ in parallel as in the one-dimensional case using $O(m / \epsilon)$ work and $O(\log n)$ depth. 
    \item Second level: We break this step into: (i) the construction of auxiliary arrays $A(u)$, and (ii) the construction of the auxiliary trees $\mathscr{T}_{aux}(u)$, for each node $u \in \mathscr{T}$. 
    \begin{enumerate}
        \item Auxiliary arrays: For each node $u \in \mathscr{T}$, we want an array $A_{aux}(u)$ that contains the leaf elements of the sub-tree rooted at $u$ sorted by y-coordinate. For an internal node $v$, this can be obtained from combining the sorted arrays of its children $\{A(w)|w \in children(v)\}$. One way to do this is to use radix sort on the union of elements in such arrays. This takes linear work and logarithmic depth on the total size of the arrays. Now, observe that at any given level of $\mathscr{T}$ the total size of auxiliary arrays is $m$. Hence, processing the nodes at each level of the tree independently in parallel accounts for $O(m)$ work and $O(\log n)$ depth. And since there are $O(1/\epsilon)$ levels in the tree, then the construction of the auxiliary arrays requires total $O(m / \epsilon)$ work and $O(\log n / \epsilon) < O(\log^2 n)$ depth\footnotemark[9]. 
        
        %In the binary case; that is, when $\epsilon = \log(n)$, this step can be done by merging 
        \item Auxiliary trees: For each node $u \in \mathscr{T}$, we want to build a one-dimensional structure $\mathscr{T}_{aux}(u)$ as in Lemma \ref{lemma:1DimensionalEpsolinTree} for the leaf elements of the sub-tree rooted at $u$, sorted by $y$-coordinate. With the arrays $A_{aux}(u)$ from the previous step, it is easy to construct such trees in parallel by processing the nodes at each level of the main tree $\mathscr{T}$ simultaneously. From Lemma \ref{lemma:1DimensionalEpsolinTree}, a tree $T_{aux}(u)$ can be constructed with $O(|A_{aux}|)$ work and $O(\log |A_{aux}|)$ depth. And at each level of $\mathscr{T}$, a total of $O(m)$ work is performed, hence $O(m / \epsilon)$ overall. On the other hand, the total depth telescopes to $O(\log n / \epsilon)$, which we bound as $O(\log^2 n)$.\footnotemark[9] 
    \end{enumerate}
\end{enumerate}

\paragraph{Query.} Consider a query rectangle $[x_1, x_2] \times [y_1, y_2]$. The query proceeds by searching for $x_1$ and $x_2$ in the main tree $\mathscr{T}$, and identify in the process the set $V_x$ of internal nodes $u$ whose corresponding leaves (determined by the sub-tree rooted at $u$) are entirely contained in the interval $[x_1, x_2]$ (and whose parent nodes do not have all their leaves in the interval). From this set, the 2-dimensional query is reduced to performing 1-dimensional queries (with the interval $[y_1, y_2]$) to the auxiliary structures $\mathscr{T}_{aux}$ at each node in $V_x$, and adding up the results. 
Let $S(u)$ denote the leaf elements in the sub-tree rooted at $u$. Then we are interested in finding the set $V_x = \{v \in T | S(v) \in S \cap [x_1, x_2] \text{ and } S(p(v)) \not\in S \cap [x_1, x_2]\}$, where $p(u)$ denotes the parent node of $u$. 

To find the set $V_x$ in parallel, we inspect each child of an internal node $u$ independently in parallel and test whether it is entirely contained in the interval $[x_1, x_2]$ or not. In an up-sweep fashion, we identify the "bounding" children such that all the children in between are fully contained in $[x_1, x_2]$, and we add such "bounded" children to $V_x$. This requires $O(n^\epsilon)$ work and $O(\epsilon \cdot \log n)$ depth. We then proceed the search recursively on the two "bounding" children performing the same work and depth per level of the tree, up until reaching the leaves of $\mathscr{T}$. Since there are $O(1 / \epsilon)$ levels in the tree, we have total $O(n^\epsilon / \epsilon)$ work and $O(\log n)$ depth. Observe that at each level of the tree, at most $O(n^\epsilon)$ nodes are added to the set $V_x$, hence the set has cardinality at most $O(n^\epsilon / \epsilon)$. 

Now, for each element on $V_x$ we perform a 1-dimensional query with the interval $[y_1, y_2]$ as in Lemma \ref{lemma:1DimensionalEpsolinTree} and we aggregate (sum) the results in a bottom-up fashion. Performing the $O(n^\epsilon / \epsilon)$ one-dimensional queries takes total $O(n^{2\epsilon} / \epsilon^2)$ work and $O(\log n)$ depth. And the final sum simply takes linear work and $O(\log n)$ depth, from which the claimed complexity follows. 
\end{proof}

If we replace the parallel geometric data structure of Lemma \ref{lemma:dataStructureBinary} with the 2-dimensional data structure of Lemma \ref{lemma:2DimensionalEpsolinTree} we obtain a parallel 2-respecting min-cut algorithm that has %$O(m + n \log n + n \log n \cdot n^\epsilon)$ 
$O(m / \epsilon + n^{1+2\epsilon}(\log n)/\epsilon^2 + n \log n)$ 
work and $O(\log^2 n)$ depth. Plugging these bounds into equations \eqref{eq:older_brother} and \eqref{eq:younger_brother}, along with the bounds of Theorem \ref{theorem:1.2}, results in our main theorem. 

\begin{theorem} 
% % Old (mistake)
% Given a weighted graph $G = (V, E)$ with $m = \Omega(n^{1+\epsilon})$ the minimum cut can be computed in parallel w.h.p. using $O((m \log n + n^{1+\epsilon})/\epsilon + n \log^5 n)$ work and $O(\log^3 n)$ depth, for any fixed $\epsilon > 0$. 
% New (fixed)
Given a weighted graph $G = (V, E)$ %with $m = \Omega(n^{1+\epsilon})$ 
the minimum cut can be computed in parallel w.h.p. using %$O(m \log n / \epsilon + n^{1+2\epsilon}\log^2 n /\epsilon^2 + n \log^5 n)$
$O(m (\log n)/ \epsilon + n^{1+2\epsilon}(\log^2 n)/\epsilon^2 + n \log^5 n)$ 
work and $O(\log^3 n)$ depth, for any fixed $\epsilon > 0$. 
\end{theorem}

By readjusting the parameter $\epsilon$ and suppressing constant scaling factors, we can obtain a work bound of $O(m \log n + n^{1+\epsilon})$ for any constant %$\epsilon > 0$. \andres{I think $\log \log n / \log n < \epsilon < 1$, not $\epsilon > 0$ (also true for \cite{gawrychowski2020note})} 
$\epsilon > c (\log \log n) / \log n$ for big enough $c$. If $m = n^{1+\Omega(1)}$, this can be simplified to $O(m \log n)$ work. 

% \begin{acks}
% This project has received funding from the European Research Council (ERC) under the European
% Unions Horizon 2020 research and innovation programme under grant agreement No 715672. Danupon
% Nanongkai and Sagnik Mukhopadhyay are also partially supported by the Swedish Research Council (Reg.~No. 2019-05622).
% \end{acks}

% \section*{Acknowledgment}
% This project has received funding from the European Research Council (ERC) under the European
% Unions Horizon 2020 research and innovation programme under grant agreement No 715672. Danupon
% Nanongkai and Sagnik Mukhopadhyay are also partially supported by the Swedish Research Council (Reg.~No. 2019-05622). 

%\section{Conclusion}

%%
%% The acknowledgments section is defined using the "acks" environment
%% (and NOT an unnumbered section). This ensures the proper
%% identification of the section in the article metadata, and the
%% consistent spelling of the heading.

%%
%% The next two lines define the bibliography style to be used, and
%% the bibliography file.
\bibliography{biblio}

%%
%% If your work has an appendix, this is the place to put it.
\appendix

\section{Proof of Lemma \ref{lemma:dataStructureBinary}}
Recall that $T_e$ denotes the sub-tree of $T$ rooted at the lower endpoint (furthest from the root) of $e$, and $w(T_e, T_f)$ is the total weight of edges between $T_e$ and $T_f$. In particular, $w(T_e) = w(T_e, T \setminus T_e)$. Let $p(u)$ denote the parent of a node $u$ in $T$. Given an edge $e = (u, p(u))$ we use $u^\downarrow$ to denote the set of nodes in the tree $T_e$. 

To prove the lemma, first, we need the following data structure.

\begin{lemma} \label{dataStructRangeTreeFull}
Given an weighted graph $G = (V, E)$, and a spanning tree $T$ of $G$, there exists a data structure that can be preprocessed in parallel with $O(m \log m)$ work and $O(\log n)$ depth, and supports the following queries with $O(\log^2 n)$ work and $O(\log n)$ depth:
\begin{itemize}
    \item \textit{\textbf{cost($u$):}} given a node $u \in V$, compute $w(T_e)$, with $e = (u, p(u))$,  
    \item \textit{\textbf{cross-cost($u, v$):}} given nodes $u$ and $v$, compute $w(T_e, T_f)$, $e = (u, p(u))$ and $f = (v, p(v))$
    \item \textit{\textbf{down-cost($u, v$):}} given edges $u$ and $v$, compute $w(T_e, V \setminus T_f)$, $e = (u, p(u))$ and $f = (v, p(v))$.
\end{itemize}
\end{lemma}
\begin{proof}
We start by computing for each node $u \in V$ its postorder number in $T$, denoted by $post(u)$, in parallel with $O(n)$ work and $O(\log n)$ depth \cite{10.5555/133889}. This produces at each node $u$ its rank in a postorder traversal of $T$, denoted by $post(u)$. Additionally, we determine for each node $u \in V$ its number of descendants, denoted by $size(u)$, with $O(n)$ work and $O(\log n)$ depth \cite{10.5555/133889}.

Let $A$ be the array constructed by setting $A[post(u)] = u$ for all $u \in V$ in parallel with the same work and depth as before. From the definition of postorder traversal, we know that the postorder traversals of the children of a node $u$ appear, from left to right, immediately before $u$ in the array $A$. 
This means that the leftmost leaf $v$ of the sub-tree rooted at $u$ can be found $size(n)$ positions left of $u$ in array $A$; i.e., $post(v) = post(u) - size(u)$. We denote this position as $start(u)$. Thus:
\begin{enumerate}
    \item $\forall$ $u \in V$, $u^\downarrow$ defines the continuous range $A[start(u):post(u)]$, 
    \item $\forall$ $u \in V$, $V - u^\downarrow$ defines two continuous ranges $A[0:start(u) - 1]$ and $A[post(u) + 1:n - 1]$
\end{enumerate}

Now, assume a coordinate plane with the $x$ and $y$ axes both labeled from 0 to $n - 1$. Suppose that graph $G$ is represented as an array of edges $A_E$. We create a new array $A_P$ in parallel, such that for each $e_i = (u, v) \in A_E$ with weight $w_i$ we set $A_P[i] = (post(u), post(v))$ with the same weight $w_i$. Array $A_P$ represents points in the plane labeled by the postorder traversal of $T$. We use $A_P$ as input to construct a \textit{parallel 2-d range searching} data structure $D$ as in Lemma \ref{lemma:2DimensionalEpsolinTree}. Setting $\epsilon = \log(n)$, the preprocessing takes $O(m \log n)$ work and $O(\log n)$ depth.

From facts (1) and (2) above, at most two queries to $D$ suffice to answer each of the cut queries from the claim. Specifically,

\textit{\textbf{cost($u$):}} This query can be answered from the sum of two \textit{range addition} queries to $D$ with ranges
    \begin{equation*}
    \begin{split}
         R_1 & = [start(u), post(u)] \times [0, start(u) - 1], \\
         R_2 & = [start(u), post(u)] \times [post(u) + 1, n - 1].
    \end{split}
    \end{equation*}
\textit{\textbf{cross-cost($u, v$):}} This query can be answered with one \textit{range addition} query to $D$ with range
    \begin{equation*}
    \begin{split}
         R & = [start(v), post(v)] \times [start(u), post(u)].
    \end{split}
    \end{equation*}
\textit{\textbf{down-cost($u, v$):}} This query can be answered from the sum of two \textit{range addition} queries to $D$ with ranges 
    \begin{equation*}
    \begin{split}
         R_1 & = [start(u), post(u)] \times [0, start(v) - 1], \\
         R_2 & = [start(u), post(u)] \times [post(v) + 1, n - 1].
    \end{split}
    \end{equation*}

As for the parallel complexity, the preprocessing cost of this structure is $O(m \log m)$ work and $O(\log n)$ depth, which mostly comes from the construction of $D$. The postorder numbering and point mapping only account for additional logarithmic depth and linear work. Accessing $post$ and $start$ can be done with constant work, hence the parallel cost of each query operation simply follows from the cost of the query in Lemma \ref{lemma:2DimensionalEpsolinTree}. 
\end{proof}

\begin{lemma} \label{lemma:1.1.1.2}
The data structure from Lemma \ref{dataStructRangeTreeFull} supports weighted \textit{cut-queries} of the form $cut(e, f)$ with $O(\log^2 n)$ work and $O(\log n)$ depth. 
\end{lemma}
\begin{proof}
Given edges $e = (u', u)$ and $f = (v', v)$, let $u$ and $v$ denote the descendants of $u'$ and $v'$ respectively. There are two possibilities for $e$ and $f$: (1) they belong to different subtrees in $T$, or (2) one edge is a descendant of the other. From the $post$ and $start$ indices created in the preprocessing step of Lemma \ref{dataStructRangeTreeFull}, we can easily check which case is satisfied, since $start(v) \leq pos(u) \leq pos(v)$ iff $u$ is in the sub-tree rooted at $v$. Then, we can compute the cut query as follows:
\begin{equation*}
cut(e, f) = 
  \begin{cases} 
   w(T_e) + w(T_f) - 2w(T_e, T_f)		& \text{if } e \not\in T_f \land f \not\in T_e \\
   w(T_e) + w(T_f) - 2w(T_e, T \setminus T_f)     & \text{if } e \in T_f \\
   w(T_e) + w(T_f) - 2w(T_f, T \setminus T_u)     & \text{if } f \in T_u
\end{cases}
\end{equation*}
where queries of the form $w(T_x)$ and $w(T_x, T_y)$ can both be answered with $O(\log^2 n)$ work and $O(\log n)$ depth. Since we are doing a constant amount of such operations per cut query, the result follows. 
\end{proof}

From Lemma \ref{lemma:1.1.1.2} and the definition of interested edges (Definition \ref{definition:interest}), the claim of Lemma \ref{lemma:dataStructureBinary} follows. 

% \subsection{Appendix section}





\end{document}
preamble.tex
\usepackage[bookmarks,colorlinks,breaklinks]{hyperref}
\hypersetup{urlcolor=blue, colorlinks=true, citecolor=green!50!black, linkcolor=blue}
\usepackage[letterpaper, left=1in, right=1in, top=0.9in, bottom=0.9in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[american]{babel}
\usepackage{etoolbox}




\usepackage[normalem]{ulem}

% Graphics
\usepackage{graphicx}
\graphicspath{{images/}{../images/}}

\usepackage{amsmath, amssymb, cases}
 \usepackage{theoremstyles}
% \usepackage{enumitem}
% \usepackage{natbib}
\usepackage{mdframed}
\usepackage{bbm}
\usepackage{bm}

%\usepackage{algorithmicx}               
%\usepackage{algorithm}
\usepackage[ruled]{algorithm}
\usepackage[noend]{algpseudocode}

 
\usepackage{microtype}

\usepackage{mdframed}
\usepackage{xcolor}

\bibliographystyle{alpha}% the recommended bibstyle

\usepackage{tikz}
\usetikzlibrary{fit, arrows, shapes, matrix, chains, positioning, backgrounds, arrows.meta, tikzmark, decorations.pathreplacing}

\input{commands}

\usepackage{mathrsfs}
biblio.bib

% Journals

% First the Full Name is given, then the abbreviation used in the AMS Math
% Reviews, with an indication if it could not be found there.
% Note the 2nd overwrites the 1st, so swap them if you want the full name.

 %{AMS}
 @article{BurkardKR96,
  author    = {Rainer E. Burkard and
               Bettina Klinz and
               R{\"{u}}diger Rudolf},
  title     = {Perspectives of Monge Properties in Optimization},
  journal   = {Discret. Appl. Math.},
  volume    = {70},
  number    = {2},
  pages     = {95--161},
  year      = {1996}
}

@article{AggarwalKMSW87,
  author    = {Alok Aggarwal and
               Maria M. Klawe and
               Shlomo Moran and
               Peter W. Shor and
               Robert E. Wilber},
  title     = {Geometric Applications of a Matrix-Searching Algorithm},
  journal   = {Algorithmica},
  volume    = {2},
  pages     = {195--208},
  year      = {1987}
}

@article{ChuzhoyGLNPS19,
  author    = {Julia Chuzhoy and
               Yu Gao and
               Jason Li and
               Danupon Nanongkai and
               Richard Peng and
               Thatchaphol Saranurak},
  title     = {A Deterministic Algorithm for Balanced Cut with Applications to Dynamic
               Connectivity, Flows, and Beyond},
  journal   = {CoRR},
  volume    = {abs/1910.08025},
  year      = {2019}
}

@article{MukhopadhyayN20,
  author    = {Sagnik Mukhopadhyay and
               Danupon Nanongkai},
  title     = {Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms},
  journal   = {CoRR},
  volume    = {abs/1911.01651},
  year      = {2019}
}

@article{HenzingerK99,
	author    = {Monika Rauch Henzinger and
	Valerie King},
	title     = {Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time
	per Operation},
	journal   = {J. {ACM}},
	volume    = {46},
	number    = {4},
	pages     = {502--516},
	year      = {1999},
	url       = {http://doi.acm.org/10.1145/320211.320215},
	doi       = {10.1145/320211.320215},
	timestamp = {Thu, 20 Nov 2003 12:28:11 +0100},
	biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jacm/HenzingerK99},
	bibsource = {dblp computer science bibliography, http://dblp.org},
	note		= {Announced at STOC 1995}
}


@article{HolmLT01,
	author    = {Jacob Holm and
	Kristian de Lichtenberg and
	Mikkel Thorup},
	title     = {Poly-logarithmic deterministic fully-dynamic algorithms for connectivity,
	minimum spanning tree, 2-edge, and biconnectivity},
	journal   = {J. {ACM}},
	volume    = {48},
	number    = {4},
	pages     = {723--760},
	year      = {2001},
	url       = {http://doi.acm.org/10.1145/502090.502095},
	doi       = {10.1145/502090.502095},
	timestamp = {Tue, 24 Jan 4445533 12:26:56 +},
	biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jacm/HolmLT01},
	bibsource = {dblp computer science bibliography, http://dblp.org},
	note		= {Announced at STOC 1998}
}


@inproceedings{Wulff-Nilsen13a,
	author    = {Christian Wulff{-}Nilsen},
	title     = {Faster Deterministic Fully-Dynamic Graph Connectivity},
	booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
	Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
	2013},
	pages     = {1757--1769},
	year      = {2013},
	url       = {http://dx.doi.org/10.1137/1.9781611973105.126},
	doi       = {10.1137/1.9781611973105.126},
	timestamp = {Wed, 12 Feb 2014 17:08:16 +0100},
	biburl    = {http://dblp.uni-trier.de/rec/bib/conf/soda/Wulff-Nilsen13a},
	bibsource = {dblp computer science bibliography, http://dblp.org}
}



@inproceedings{KapronKM13,
	author    = {Bruce M. Kapron and
	Valerie King and
	Ben Mountjoy},
	title     = {Dynamic graph connectivity in polylogarithmic worst case time},
	booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
	Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
	2013},
	pages     = {1131--1142},
	year      = {2013},
	url       = {https://doi.org/10.1137/1.9781611973105.81},
	doi       = {10.1137/1.9781611973105.81},
	timestamp = {Wed, 14 Nov 2018 10:51:42 +0100},
	biburl    = {https://dblp.org/rec/bib/conf/soda/KapronKM13},
	bibsource = {dblp computer science bibliography, https://dblp.org}
}


@inproceedings{NanongkaiSW17,
  author    = {Danupon Nanongkai and
               Thatchaphol Saranurak and
               Christian Wulff{-}Nilsen},
  title     = {Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time},
  booktitle = {{FOCS}},
  pages     = {950--961},
  publisher = {{IEEE} Computer Society},
  year      = {2017}
}


@article{MunroNV16,
  author    = {J. Ian Munro and
               Yakov Nekrich and
               Jeffrey Scott Vitter},
  title     = {Fast construction of wavelet trees},
  journal   = {Theor. Comput. Sci.},
  volume    = {638},
  pages     = {91--97},
  year      = {2016}
}

@article{Overmars88,
  author    = {Mark H. Overmars},
  title     = {Efficient Data Structures for Range Searching on a Grid},
  journal   = {J. Algorithms},
  volume    = {9},
  number    = {2},
  pages     = {254--275},
  year      = {1988},
  url       = {https://doi.org/10.1016/0196-6774(88)90041-7},
  doi       = {10.1016/0196-6774(88)90041-7},
}

@inproceedings{gawrychowski2021note,
  title={A note on a recent algorithm for minimum cut},
  author={Gawrychowski, Pawe{\l} and Mozes, Shay and Weimann, Oren},
  booktitle={Symposium on Simplicity in Algorithms (SOSA)},
  pages={74--79},
  year={2021},
  organization={SIAM}
}

@inproceedings{GMW19,
  author    = {Pawel Gawrychowski and
               Shay Mozes and
               Oren Weimann},
  title     = {Minimum Cut in O(m log{\({^2}\)} n) Time},
  booktitle = {{ICALP}},
  series    = {LIPIcs},
  volume    = {168},
  pages     = {57:1--57:15},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2020}
}

@inproceedings{CP10,
  author    = {Timothy M. Chan and
               Mihai Patrascu},
  title     = {Counting Inversions, Offline Orthogonal Range Counting, and Related
               Problems},
  booktitle = {Proceedings of the 21st {SODA}},
  pages     = {161--173},
  year      = {2010},
  url       = {https://doi.org/10.1137/1.9781611973075.15},
  doi       = {10.1137/1.9781611973075.15},
  }
@inproceedings{BGKS15,
  author    = {Maxim A. Babenko and
               Pawel Gawrychowski and
               Tomasz Kociumaka and
               Tatiana Starikovskaya},
  title     = {Wavelet Trees Meet Suffix Trees},
  booktitle = {Proceedings of the 26th SODA},
  pages     = {572--591},
  year      = {2015},
  url       = {https://doi.org/10.1137/1.9781611973730.39},
  doi       = {10.1137/1.9781611973730.39},
}

@article{HT84,
  author    = {Dov Harel and
               Robert Endre Tarjan},
  title     = {Fast Algorithms for Finding Nearest Common Ancestors},
  journal   = {{SIAM} J. Comput.},
  volume    = {13},
  number    = {2},
  pages     = {338--355},
  year      = {1984},
  url       = {https://doi.org/10.1137/0213024},
  doi       = {10.1137/0213024},
}
@article{Chaz88,
  author    = {Bernard Chazelle},
  title     = {A Functional Approach to Data Structures and Its Use in Multidimensional
               Searching},
  journal   = {{SIAM} J. Comput.},
  volume    = {17},
  number    = {3},
  pages     = {427--462},
  year      = {1988},
  url       = {https://doi.org/10.1137/0217026},
  doi       = {10.1137/0217026},
}

@inproceedings{ChanP10,
	author    = {Timothy M. Chan and
	Mihai Patrascu},
	title     = {Counting Inversions, Offline Orthogonal Range Counting, and Related
	Problems},
	booktitle = {{SODA}},
	pages     = {161--173},
	publisher = {{SIAM}},
	year      = {2010}
}


@article{FeigenbaumKMSZ05,
	author    = {Joan Feigenbaum and
	Sampath Kannan and
	Andrew McGregor and
	Siddharth Suri and
	Jian Zhang},
	title     = {On graph problems in a semi-streaming model},
	journal   = {Theor. Comput. Sci.},
	volume    = {348},
	number    = {2-3},
	pages     = {207--216},
	year      = {2005}
}

@inproceedings{DasSarmaHKKNPPW11,
	author    = {Atish Das Sarma and
	Stephan Holzer and
	Liah Kor and
	Amos Korman and
	Danupon Nanongkai and
	Gopal Pandurangan and
	David Peleg and
	Roger Wattenhofer},
	title     = {Distributed verification and hardness of distributed approximation},
	booktitle = {{STOC}},
	pages     = {363--372},
	publisher = {{ACM}},
	year      = {2011}
}

@article{LovettS19,
	author    = {Antonio Molina Lovett and
	Bryce Sandlund},
	title     = {A Simple Algorithm for Minimum Cuts in Near-Linear Time},
	journal   = {CoRR},
	volume    = {abs/1908.11829},
	year      = {2019}
}


@article{GoelKP12,
	author    = {Ashish Goel and
	Michael Kapralov and
	Ian Post},
	title     = {Single pass sparsification in the streaming model with edge deletions},
	journal   = {CoRR},
	volume    = {abs/1203.4900},
	year      = {2012}
}

@inproceedings{AhnGM12-soda,
	author    = {Kook Jin Ahn and
	Sudipto Guha and
	Andrew McGregor},
	title     = {Analyzing graph structure via linear measurements},
	booktitle = {{SODA}},
	pages     = {459--467},
	publisher = {{SIAM}},
	year      = {2012}
}

@inproceedings{AhnGM12-pods,
	author    = {Kook Jin Ahn and
	Sudipto Guha and
	Andrew McGregor},
	title     = {Graph sketches: sparsification, spanners, and subgraphs},
	booktitle = {{PODS}},
	pages     = {5--14},
	publisher = {{ACM}},
	year      = {2012}
}

@article{Zelke11,
	author    = {Mariano Zelke},
	title     = {Intractability of min- and max-cut in streaming graphs},
	journal   = {Inf. Process. Lett.},
	volume    = {111},
	number    = {3},
	pages     = {145--150},
	year      = {2011}
}



article{GhaffariNT20,
	author    = {Mohsen Ghaffari and
	Krzysztof Nowicki and
	Mikkel Thorup},
	title     = {Faster Algorithms for Edge Connectivity via Random 2-Out Contractions},
	journal   = {CoRR},
	volume    = {abs/1909.00844},
	year      = {2019}
}



@inproceedings{GhaffariNT20,
	author    = {Mohsen Ghaffari and
Krzysztof Nowicki and
Mikkel Thorup},
title     = {Faster Algorithms for Edge Connectivity via Random 2-Out Contractions},
	booktitle = {{SODA}},
	publisher = {{SIAM}},
	year      = {2020}
}

@inproceedings{HenzingerRW17,
	author    = {Monika Henzinger and
	Satish Rao and
	Di Wang},
	title     = {Local Flow Partitioning for Faster Edge Connectivity},
	booktitle = {{SODA}},
	pages     = {1919--1938},
	publisher = {{SIAM}},
	year      = {2017}
}

@article{KawarabayashiT19,
	author    = {Ken{-}ichi Kawarabayashi and
	Mikkel Thorup},
	title     = {Deterministic Edge Connectivity in Near-Linear Time},
	journal   = {J. {ACM}},
	volume    = {66},
	number    = {1},
	pages     = {4:1--4:50},
	year      = {2019},
	note	= {announced at STOC'15}
}

@inproceedings{AssadiCK19,
	author    = {Sepehr Assadi and
	Yu Chen and
	Sanjeev Khanna},
	title     = {Polynomial pass lower bounds for graph streaming algorithms},
	booktitle = {{STOC}},
	pages     = {265--276},
	publisher = {{ACM}},
	year      = {2019}
}


@article{Chazelle88,
	author    = {Bernard Chazelle},
	title     = {A Functional Approach to Data Structures and Its Use in Multidimensional
	Searching},
	journal   = {{SIAM} J. Comput.},
	volume    = {17},
	number    = {3},
	pages     = {427--462},
	year      = {1988}, 
	note	= {announced at FOCS'85}
}

@phdthesis{Karger_thesis,
	author = {Karger, David Ron},
	title = {Random Sampling in Graph Optimization Problems},
	year = {1995},
	note = {UMI Order No. GAX95-16851},
	publisher = {Stanford University},
	address = {Stanford, CA, USA},
} 


@article{Karger99-skeleton,
	author    = {David R. Karger},
	title     = {Random Sampling in Cut, Flow, and Network Design Problems},
	journal   = {Math. Oper. Res.},
	volume    = {24},
	number    = {2},
	pages     = {383--413},
	year      = {1999},
	note	= {announced at STOC'94}
}

@inproceedings{Matula93,
	author    = {David W. Matula},
	title     = {A Linear Time 2+epsilon Approximation Algorithm for Edge Connectivity},
	booktitle = {{SODA}},
	pages     = {500--504},
	publisher = {{ACM/SIAM}},
	year      = {1993}
}

inproceedings{AssadiCK19,
	author    = {Sepehr Assadi and
	Yu Chen and
	Sanjeev Khanna},
	title     = {Polynomial pass lower bounds for graph streaming algorithms},
	booktitle = {{STOC}},
	pages     = {265--276},
	publisher = {{ACM}},
	year      = {2019}
}

@article{ST83,
  author    = {Daniel Dominic Sleator and
               Robert Endre Tarjan},
  title     = {A Data Structure for Dynamic Trees},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {26},
  number    = {3},
  pages     = {362--391},
  year      = {1983},
  url       = {https://doi.org/10.1016/0022-0000(83)90006-5},
  doi       = {10.1016/0022-0000(83)90006-5},
}

@article{Kar00,
  author    = {David R. Karger},
  title     = {Minimum cuts in near-linear time},
  journal   = {J. {ACM}},
  volume    = {47},
  number    = {1},
  pages     = {46--76},
  year      = {2000},
  url       = {https://doi.org/10.1145/331605.331608},
  doi       = {10.1145/331605.331608},
  note		= {announced at STOC'96}
}

@inproceedings{RubinsteinSW18,
  author    = {Aviad Rubinstein and
               Tselil Schramm and
               S. Matthew Weinberg},
  title     = {Computing Exact Minimum Cuts Without Knowing the Graph},
  booktitle = {Proceedings of the 9th {ITCS}},
  pages     = {39:1--39:16},
  year      = {2018},
  url       = {https://doi.org/10.4230/LIPIcs.ITCS.2018.39},
  doi       = {10.4230/LIPIcs.ITCS.2018.39},
}

@article{Thorup07,
  author    = {Mikkel Thorup},
  title     = {Fully-Dynamic Min-Cut},
  journal   = {Combinatorica},
  volume    = {27},
  number    = {1},
  pages     = {91--127},
  year      = {2007},
  url       = {https://doi.org/10.1007/s00493-007-0045-2},
  doi       = {10.1007/s00493-007-0045-2},
}

@article{KLMMS17,
  author    = {Michael Kapralov and
               Yin Tat Lee and
               Cameron Musco and
               Christopher Musco and
               Aaron Sidford},
  title     = {Single Pass Spectral Sparsification in Dynamic Streams},
  journal   = {{SIAM} J. Comput.},
  volume    = {46},
  number    = {1},
  pages     = {456--477},
  year      = {2017},
  url       = {https://doi.org/10.1137/141002281},
  doi       = {10.1137/141002281},
}

@ARTICLE{Vit85,
    author = {Jeffrey Scott Vitter},
    title = {Random sampling with a reservoir},
    journal = {ACM Transactions on Mathematical Software},
    year = {1985},
    volume = {11},
    pages = {37--57}
}
@inproceedings{10.5555/314464.314661,
author = {Raman, Rajeev and Vishkin, Uzi},
title = {Optimal Randomized Parallel Algorithms for Computing the Row Maxima of a Totally Monotone Matrix},
year = {1994},
isbn = {0898713293},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {613–621},
numpages = {9},
location = {Arlington, Virginia, USA},
series = {SODA '94}
}
 
@article{KachitvichyanukulS88,
author = {Kachitvichyanukul, Voratas and Schmeiser, Bruce W.},
title = {Binomial Random Variate Generation},
year = {1988},
publisher = {Association for Computing Machinery},
volume = {31},
number = {2},
journal = {Commun. ACM},
month = feb,
pages = {216–222},
numpages = {7}
}

@article{Farach-ColtonT15,
  author    = {Martin Farach{-}Colton and
               Meng{-}Tsung Tsai},
  title     = {Exact Sublinear Binomial Sampling},
  journal   = {Algorithmica},
  volume    = {73},
  number    = {4},
  pages     = {637--651},
  year      = {2015}
}
 
@inproceedings{10.1145/97444.97693,
author = {Aggarwal, A. and Kravets, D. and Park, J. and Sen, S.},
title = {Parallel Searching in Generalized Monge Arrays with Applications},
year = {1990},
isbn = {0897913701},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/97444.97693},
doi = {10.1145/97444.97693},
booktitle = {Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures},
pages = {259–268},
numpages = {10},
location = {Island of Crete, Greece},
series = {SPAA '90}
}
 
 @article{AndersonB2021,
  author    = {Daniel Anderson and
               Guy E. Blelloch},
  title     = {Parallel Minimum Cuts in O(m log2
(n)) Work and Low Depth},
  journal   = {CoRR},
  volume    = {abs/2102.05301},
  year      = {2021}
}
 
 @mastersthesis{LopezMartinez1512083,
   author = {López Martínez, Andr\'es},
   institution = {KTH, School of Electrical Engineering and Computer Science (EECS)},
   pages = {83},
   school = {KTH, School of Electrical Engineering and Computer Science (EECS)},
   title = {Parallel Minimum Cuts : An improved CREW PRAM algorithm},
   series = {TRITA-EECS-EX},
   number = {2020:821},
   year = {2020}
}

 
 @article{DBLP:journals/corr/abs-1807-09524,
  author    = {Barbara Geissmann and
               Lukas Gianinazzi},
  title     = {Parallel Minimum Cuts in Near-linear Work and Low Depth},
  journal   = {CoRR},
  volume    = {abs/1807.09524},
  year      = {2018},
  url       = {http://arxiv.org/abs/1807.09524},
  archivePrefix = {arXiv},
  eprint    = {1807.09524},
  timestamp = {Mon, 13 Aug 2018 16:46:15 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/abs-1807-09524},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{10.1145/3210377.3210393,
author = {Geissmann, Barbara and Gianinazzi, Lukas},
title = {Parallel Minimum Cuts in Near-Linear Work and Low Depth},
year = {2018},
isbn = {9781450357999},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3210377.3210393},
doi = {10.1145/3210377.3210393},
booktitle = {Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {1–11},
numpages = {11},
keywords = {parallel algorithms, minimum path data structure, minimum cut, cache-oblivious algorithms, graph algorithms},
location = {Vienna, Austria},
series = {SPAA ’18}
}

@article{DBLP:journals/corr/cs-DS-9812007,
  author    = {David R. Karger},
  title     = {Minimum Cuts in Near-Linear Time},
  journal   = {CoRR},
  volume    = {cs.DS/9812007},
  year      = {1998},
  url       = {http://arxiv.org/abs/cs.DS/9812007},
  timestamp = {Mon, 13 Aug 2018 16:47:20 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/cs-DS-9812007},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{10.1145/331605.331608,
author = {Karger, David R.},
title = {Minimum Cuts in Near-Linear Time},
year = {2000},
issue_date = {Jan. 2000},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {47},
number = {1},
issn = {0004-5411},
url = {https://doi.org/10.1145/331605.331608},
doi = {10.1145/331605.331608},
journal = {J. ACM},
month = jan,
pages = {46–76},
numpages = {31},
keywords = {connectivity, tree packing, min-cut, Monte Carlo algorithm, optimization},
addendum = {Announced at STOC'96}
}
  
@misc{lovett2019simple,
    title={A Simple Algorithm for Minimum Cuts in Near-Linear Time},
    author={Antonio Molina Lovett and Bryce Sandlund},
    year={2019},
    eprint={1908.11829},
    archivePrefix={arXiv},
    primaryClass={cs.DS}
}

@InProceedings{bhardwaj2020simple,
  author =	{Nalin Bhardwaj and Antonio J. Molina Lovett and Bryce Sandlund},
  title =	{{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12259},
  URN =		{urn:nbn:de:0030-drops-122594},
  doi =		{10.4230/LIPIcs.SWAT.2020.12},
  annote =	{Keywords: minimum cut, sparsification, near-linear time, packing}
}

@inproceedings{bhardwaj_et_al:LIPIcs:2020:12259,
  author =	{Nalin Bhardwaj and Antonio J. Molina Lovett and Bryce Sandlund},
  title =	{{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
  booktitle={17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  year={2020},
  organization={Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik}
}

@article{SLEATOR1983362,
title = "A data structure for dynamic trees",
journal = "Journal of Computer and System Sciences",
volume = "26",
number = "3",
pages = "362 - 391",
year = "1983",
issn = "0022-0000",
doi = "https://doi.org/10.1016/0022-0000(83)90006-5",
url = "http://www.sciencedirect.com/science/article/pii/0022000083900065",
author = "Daniel D. Sleator and Robert Endre Tarjan",
abstract = "A data structure is proposed to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Each operation requires O(log n) time. Using this data structure, new fast algorithms are obtained for the following problems: 1.(1) Computing nearest common ancestors.2.(2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows.3.(3) Computing certain kinds of constrained minimum spanning trees.4.(4) Implementing the network simplex algorithm for minimum-cost flows. The most significant application is (2); an O(mn log n)-time algorithm is obtained to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs."
}

@inproceedings{mukhopadhyay2019weighted,
author = {Mukhopadhyay, Sagnik and Nanongkai, Danupon},
title = {Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms},
year = {2020},
isbn = {9781450369794},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3357713.3384334},
doi = {10.1145/3357713.3384334},
abstract = {Consider the following 2-respecting min-cut problem. Given any weighted graph G and its spanning tree T, find the minimum cut among the cuts that contain at most two edges in T. This problem is an important subroutine in Karger’s celebrated randomized near-linear-time min-cut algorithm [STOC’96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs. – An O(mlog2 n/loglogn + nlog6 n)-time sequential algorithm improving Karger’s long-standing O(m log3 n) and O(nlog6 n + mlog2 nlog(n2/m)/loglogn) bounds when the input graph is not extremely sparse or dense. Improvements over Karger’s bounds were previously known only under a rather strong assumption that the input graph is simple (unweighted without parallel edges) [Henzinger, Rao, Wang, SODA’17; Ghaffari, Nowicki, Thorup, SODA’20]. For unweighted graphs (possibly with parallel edges) and using bit operations, our bound can be further improved to O(mlog1.5 n/loglogn + nlog6 n).  – An algorithm that requires \~{O}(n) cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein, Schramm, and Weinberg [ITCS’18], who obtained a similar bound for simple graphs. Our bound is tight up to polylogarithmic factors. – A streaming algorithm that requires \~{O}(n) space and O(logn) passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass \~{O}(n)-space algorithm on simple graphs [Rubinstein&nbsp;et&nbsp;al., ITCS’18] (observed by Assadi, Chen, and Khanna [STOC’19]). Our approach exploits some cute structural properties so that it only needs to compute the values of \~{O}(n) cuts corresponding to removing \~{O}(n) pairs of tree edges, an operation that can be done quickly in many settings. This is in contrast to the techniques used by Karger and Lovett-Sandlund to solve 2-respecting min-cut where information about many more cuts is computed, stored in and accessed from sophisticated data-structures.},
booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
pages = {496–509},
numpages = {14},
keywords = {cut-query model, min-cut, sequential model, streaming model, range-query data-structure},
location = {Chicago, IL, USA},
series = {STOC 2020}
}

@ARTICLE{Chazelle86fractionalcascading,
    author = {Bernard Chazelle and Leonidas J. Guibas},
    title = {Fractional cascading: I. A data structuring technique},
    journal = {Algorithmica},
    year = {1986},
    volume = {1},
    pages = {133--162}
}

@article{Sun_2019,
   title={Parallel Range, Segment and Rectangle Queries with Augmented Maps},
   ISBN={9781611975499},
   url={http://dx.doi.org/10.1137/1.9781611975499.13},
   DOI={10.1137/1.9781611975499.13},
   journal={Proceedings of the 21st ALENEX},
   publisher={Society for Industrial and Applied Mathematics},
   author={Sun, Yihan and Blelloch, Guy E.},
   year={2019},
   pages={159–173}
}

@article{doi:10.1080/01495730108935276,
author = {Datta, Amitava},
title = {Efficient Parallel Range Searching and Partitioning Algorithms*},
journal = {Parallel Algorithms and Applications},
volume = {16},
number = {4},
pages = {301-317},
year  = {2001},
publisher = {Taylor & Francis},
doi = {10.1080/01495730108935276},

URL = { 
        https://doi.org/10.1080/01495730108935276
},
eprint = { 
        https://doi.org/10.1080/01495730108935276
}
}

@book{10.5555/133889,
author = {J\'{a}J\'{a}, Joseph},
title = {An Introduction to Parallel Algorithms},
pages = {62-65},
year = {1992},
isbn = {0201548569},
publisher = {Addison Wesley Longman Publishing Co., Inc.},
address = {USA}
}

@article{SHILOACH198188,
title = "Finding the maximum, merging, and sorting in a parallel computation model",
journal = "Journal of Algorithms",
volume = "2",
number = "1",
pages = "88 - 102",
year = "1981",
issn = "0196-6774",
doi = "https://doi.org/10.1016/0196-6774(81)90010-9",
url = "http://www.sciencedirect.com/science/article/pii/0196677481900109",
author = "Yossi Shiloach and Uzi Vishkin",
abstract = "A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of O(np + log logp); (optimal for p ≤ nlog log n). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of O(np + log n) for p ≤ n (optimal for p ≤ nlog n), O(logmlogpn) for p ≥ n(= O(k) if p = m1kn, k > 1). 3. Sorting n elements within a depth of O(nplogn + lognlogp) for p ≤ n, (optimal for p ≤ nlog n). O(log2nlogpn) + logn) for p ≥ n (= O(k logn) if p = n1+1k, k > 1). The depth of O(klogn) for p = n1+1k processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657–661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669–673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons."
}

@article{10.1137/0217049,
author = {Cole, Richard},
title = {Parallel Merge Sort},
year = {1988},
issue_date = {August 1988},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
volume = {17},
number = {4},
issn = {0097-5397},
url = {https://doi.org/10.1137/0217049},
doi = {10.1137/0217049},
journal = {SIAM J. Comput.},
month = aug,
pages = {770–785},
numpages = {16}
}
  
@article{HALPERIN1996395,
title = "An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM",
journal = "Journal of Computer and System Sciences",
volume = "53",
number = "3",
pages = "395 - 416",
year = "1996",
issn = "0022-0000",
doi = "https://doi.org/10.1006/jcss.1996.0078",
url = "http://www.sciencedirect.com/science/article/pii/S0022000096900781",
author = "Shay Halperin and Uri Zwick",
abstract = "Improving a long chain of works, we obtain a randomised EREW PRAM algorithm for finding the connected components of a graphG=(V, E) withnvertices andmedges inO(logn) time using an optimal number ofO((m+n)/logn) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not complete inO(logn) time iso(n−c) for anyc>0."
}

@phdthesis{Karger:Thesis,
        author = {David R. Karger},
	title = {Random Sampling in Graph Optimization Problems},
	school = {Stanford University},
	year = {1994},
	address = {Stanford, CA 94305},
        brag = {Winner, ACM Doctoral Dissertation Award, 1995.  To be
                  published by Springer Verlag},
        ps = {http://people.csail.mit.edu/karger/Papers/thesis.ps},
cat:multiple =	{Theory;Cuts and Flows},
abstract = {The representative random sample is a central concept of statistics. It is often possible to
gather a great deal of information about a large population by examining a small sample
randomly drawn from it. This approach has obvious advantages in reducing the investiga
tor's work, both in gathering and in analyzing the data.
We apply the concept of a representative sample to combinatorial optimization. Our
general technique is to generate small random representative subproblems and solve them
in lieu of the original ones, producing approximately correct answers which may then be
refined to correct ones at little additional cost. Our focus is optimization problems on
undirected graphs. Highlights of our results include	
\begin{itemize}
\item The first (randomized) linear time minimum spanning tree algorithm
\item A (randomized) minimum cut algorithm with running time roughly $O(n^2)$ as compared
to previous roughly $O(n^3)$ time bounds, as well as the first algorithm for finding all
approximately minimal cuts and multiway cuts
\item An efficient parallelization of the minimum cut algorithm, providing the first parallel
(RNC) algorithm for minimum cuts
\item The first proof that minimum cuts can be found deterministically in parallel (NC)
\item  Reliability theorems tightly bounding the connectivities and bandwidths in networks
with random edge failures, and a fully polynomial
time approximation scheme for estimating all-terminal reliability---the probability a particular graph remains connected
under edge failures
\item A linear time algorithm for approximating minimum cuts to within $1+\epsilon$ and a linear
processor parallel algorithm for $1+\epsilon$
approximation, and fast algorithms for approximat
ing $s$-$t$ minimum cuts and maximum Flows}}

@inproceedings{10.5555/314464.314582,
author = {Karger, David R.},
title = {Using Randomized Sparsification to Approximate Minimum Cuts},
year = {1994},
isbn = {0898713293},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {424–432},
numpages = {9},
location = {Arlington, Virginia, USA},
series = {SODA ’94}
}
  
@inproceedings{KargerGlobalMincutsRNC,
author = {Karger, David},
year = {1993},
month = {01},
pages = {21-30},
title = {Global Min-cuts in $RNC$ and Other Ramifications of a Simple Mincut Algorithm},
journal = {Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
doi = {10.1145/313559.313605}
}

@article{CHONG200333,
title = "Improving the efficiency of parallel minimum spanning tree algorithms",
journal = "Discrete Applied Mathematics",
volume = "126",
number = "1",
pages = "33 - 54",
year = "2003",
note = "5th Annual International Computing and combinatorics Conference",
issn = "0166-218X",
doi = "https://doi.org/10.1016/S0166-218X(02)00560-7",
url = "http://www.sciencedirect.com/science/article/pii/S0166218X02005607",
author = "Ka Wong Chong and Yijie Han and Yoshihide Igarashi and Tak Wah Lam",
keywords = "Parallel algorithms, Graph algorithms, Minimum spanning trees, Connected components, PRAM",
abstract = "This paper presents results which improve the efficiency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(logn) time with O((m+n)logn) operations. Our CRCW PRAM algorithm runs in O(logn) time with O((m+n)loglogn) operations. We also show that for dense graphs we can achieve O(logn) time with O(n2) operations on the EREW PRAM."
}

@article{HAO1994424,
title = "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph",
journal = "Journal of Algorithms",
volume = "17",
number = "3",
pages = "424 - 446",
year = "1994",
issn = "0196-6774",
doi = "https://doi.org/10.1006/jagm.1994.1043",
url = "http://www.sciencedirect.com/science/article/pii/S0196677484710431",
author = "J.X. Hao and J.B. Orlin",
abstract = "We consider the problem of finding the minimum capacity cut in a directed network G with n nodes. This problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. One can use a maximum flow problem to find a minimum cut separating a designated source node s from a designated sink node t, and by varying the sink node one can find a minimum cut in G as a sequence of at most 2n − 2 maximum flow problems. We then show how to reduce the running time of these 2n − 2 maximum flow algorithms to the running time for solving a single maximum flow problem. The resulting running time is O(nm log(n2/m)) for finding the minimum cut in either a directed or an undirected network."
}

@article{doi:10.1137/0405004,
author = {Nagamochi, Hiroshi. and Ibaraki, Toshihide.},
title = {Computing Edge-Connectivity in Multigraphs and Capacitated Graphs},
journal = {SIAM Journal on Discrete Mathematics},
volume = {5},
number = {1},
pages = {54-66},
year = {1992},
doi = {10.1137/0405004},

URL = { 
        https://doi.org/10.1137/0405004
    
},
eprint = { 
        https://doi.org/10.1137/0405004
    
}
}

@article{DBLP:journals/corr/KawarabayashiT14,
  author    = {Ken{-}ichi Kawarabayashi and
               Mikkel Thorup},
  title     = {Deterministic Global Minimum Cut of a Simple Graph in Near-Linear
               Time},
  journal   = {CoRR},
  volume    = {abs/1411.5123},
  year      = {2014},
  url       = {http://arxiv.org/abs/1411.5123},
  archivePrefix = {arXiv},
  eprint    = {1411.5123},
  timestamp = {Mon, 13 Aug 2018 16:46:43 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/KawarabayashiT14},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@article{10.1145/234533.234534,
 author = {Karger, David R. and Stein, Clifford},
 title = {A New Approach to the Minimum Cut Problem},
 year = {1996},
 issue_date = {July 1996},
 publisher = {Association for Computing Machinery},
 address = {New York, NY, USA},
 volume = {43},
 number = {4},
 issn = {0004-5411},
 url = {https://doi.org/10.1145/234533.234534},
 doi = {10.1145/234533.234534},
 journal = {J. ACM},
 month = jul,
 pages = {601–640},
 numpages = {40},
 keywords = {graph algorithm, parallel computing, minimum cut, randomized algorithm, network reliability}
}

@inproceedings{10.1145/167088.167281,
author = {Karger, David R. and Stein, Clifford},
title = {An \~{O}(N2) Algorithm for Minimum Cuts},
year = {1993},
isbn = {0897915917},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/167088.167281},
doi = {10.1145/167088.167281},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing},
pages = {757–765},
numpages = {9},
location = {San Diego, California, USA},
series = {STOC ’93}
}
  
@InProceedings{10.1007/978-3-319-57586-5_24,
author="Geissmann, Barbara
and Gianinazzi, Lukas",
editor="Fotakis, Dimitris
and Pagourtzis, Aris
and Paschos, Vangelis Th.",
title="Cache Oblivious Minimum Cut",
booktitle="Algorithms and Complexity",
year="2017",
publisher="Springer International Publishing",
address="Cham",
pages="285--296",
abstract="We show how to compute the minimum cut of a graph cache-efficiently. Let B be the width of a cache line and M be the size of the cache. On a graph with V vertices and E edges, we give a cache oblivious algorithm that incurs {\$}{\$}O({\backslash}lceil {\backslash}frac{\{}E{\}}{\{}B{\}} ({\backslash}log ^4 E) {\backslash}log {\_}{\{}M/B{\}} E{\backslash}rceil ){\$}{\$}cache misses and a simpler one that incurs {\$}{\$}O({\backslash}lceil {\backslash}frac{\{}V^2{\}}{\{}B{\}} {\backslash}log ^3 V{\backslash}rceil ){\$}{\$}cache misses.",
isbn="978-3-319-57586-5"
}

@book{colbourn1987combinatorics,
  title={The combinatorics of network reliability},
  author={Colbourn, C.J.},
  isbn={9780195049206},
  lccn={lc87005691},
  series={International Series of Monographs on Computer Science Series},
  url={https://books.google.com.mx/books?id=UajCAAAAIAAJ},
  year={1987},
  publisher={Oxford University Press, Incorporated}
}

@inproceedings{10.1145/160688.160704,
 author = {Botafogo, Rodrigo A.},
 title = {Cluster Analysis for Hypertext Systems},
 year = {1993},
 isbn = {0897916050},
 publisher = {Association for Computing Machinery},
 address = {New York, NY, USA},
 url = {https://doi.org/10.1145/160688.160704},
 doi = {10.1145/160688.160704},
 booktitle = {Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval},
 pages = {116–125},
 numpages = {10},
 keywords = {structural analysis, clustering, hypertext, aggregation, graph theory},
 location = {Pittsburgh, Pennsylvania, USA},
 series = {SIGIR ’93}
}

@InProceedings{10.1007/BFb0025872,
author="Chatterjee, Siddhartha
and Gilbert, John R.
and Schreiber, Robert
and Sheffler, Thomas J.",
editor="Pingali, Keshav
and Banerjee, Utpal
and Gelernter, David
and Nicolau, Alex
and Padua, David",
title="Array distribution in data-parallel programs",
booktitle="Languages and Compilers for Parallel Computing",
year="1995",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="76--91",
abstract="We consider distribution at compile time of the array data in a distributed-memory implementation of a data-parallel program written in a language like Fortran 90. We allow dynamic redistribution of data and define a heuristic algorithmic framework that chooses distribution parameters to minimize an estimate of program completion time. We represent the program as an alignment-distribution graph. We propose a divide-and-conquer algorithm for distribution that initially assigns a common distribution to each node of the graph and successively refines this assignment, taking computation, realignment, and redistribution costs into account. We explain how to estimate the effect of distribution on computation cost and how to choose a candidate set of distributions. We present the results of an implementation of our algorithms on several test problems.",
isbn="978-3-540-49134-7"
}

@article{graphCutsImageProcessing,
author = {Zdimalova, Maria and Z., Kriv and Bohumel, T.},
year = {2015},
month = {01},
pages = {774-786},
title = {Graph cuts in image processing},
journal = {APLIMAT 2015 - 14th Conference on Applied Mathematics, Proceedings}
}

@article{10.1145/321812.321815,
author = {Brent, Richard P.},
title = {The Parallel Evaluation of General Arithmetic Expressions},
year = {1974},
issue_date = {April 1974},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {21},
number = {2},
issn = {0004-5411},
url = {https://doi.org/10.1145/321812.321815},
doi = {10.1145/321812.321815},
journal = {J. ACM},
month = apr,
pages = {201–206},
numpages = {6}
}
  
@book{shun2017shared,
  title={Shared-Memory Parallelism Can be Simple, Fast, and Scalable},
  author={Shun, J.},
  isbn={9781970001891},
  series={ACM Books},
  url={https://books.google.se/books?id=WQ8oDwAAQBAJ},
  year={2017},
  publisher={Association for Computing Machinery and Morgan \& Claypool Publishers}
}

@book{rajasekaran2007handbook,
  title={Handbook of Parallel Computing: Models, Algorithms and Applications},
  author={Rajasekaran, S. and Reif, J.},
  isbn={9781420011296},
  lccn={2007025276},
  series={Chapman \& Hall/CRC Computer and Information Science Series},
  url={https://books.google.se/books?id=OF9hk4oC6FIC},
  year={2007},
  publisher={CRC Press}
}

@book{schmidt2017parallel,
  title={Parallel Programming: Concepts and Practice},
  author={Schmidt, B. and Gonzalez-Dominguez, J. and Hundt, C. and Schlarb, M.},
  isbn={9780128044865},
  url={https://books.google.se/books?id=-y9HDgAAQBAJ},
  year={2017},
  publisher={Elsevier Science}
}

@article{GuyEBlelloch,
author = {Blelloch, Guy E.},
year = {1996},
month = {03},
pages = {85-97},
title = {Programming Parallel Algorithms},
volume = {39},
journal = {Commun. ACM},
doi = {10.1145/227234.227246}
}

@inproceedings{herlihy2007multicore,
  title={The multicore revolution},
  author={Herlihy, Maurice},
  booktitle={International Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages={1--8},
  year={2007},
  organization={Springer}
}

@article{10.2307/3690490,
 ISSN = {0364765X, 15265471},
 URL = {http://www.jstor.org/stable/3690490},
 abstract = {We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to 1 + O(√log n)/k).},
 author = {David R. Karger},
 journal = {Mathematics of Operations Research},
 number = {2},
 pages = {383--413},
 publisher = {INFORMS},
 title = {Random Sampling in Cut, Flow, and Network Design Problems},
 volume = {24},
 year = {1999}
}

@book{padua2011encyclopedia,
  title={Encyclopedia of parallel computing},
  author={Padua, David},
  year={2011},
  publisher={Springer Science \& Business Media}
}

@article{10.1145/322217.322232,
author = {Ladner, Richard E. and Fischer, Michael J.},
title = {Parallel Prefix Computation},
year = {1980},
issue_date = {Oct. 1980},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {27},
number = {4},
issn = {0004-5411},
url = {https://doi.org/10.1145/322217.322232},
doi = {10.1145/322217.322232},
journal = {J. ACM},
month = oct,
pages = {831–838},
numpages = {8}
}
  
@article{10.2307/170274,
 ISSN = {0030364X, 15265463},
 URL = {http://www.jstor.org/stable/170274},
 abstract = {Parallel algorithms are given for scheduling problems such as scheduling to minimize the number of tardy jobs, job sequencing with deadlines, scheduling to minimize earliness and tardiness penalties, channel assignment, and minimizing the mean finish time. The shared memory model of parallel computers is used to obtain fast algorithms.},
 author = {Eliezer Dekel and Sartaj Sahni},
 journal = {Operations Research},
 number = {1},
 pages = {24--49},
 publisher = {INFORMS},
 title = {Parallel Scheduling Algorithms},
 volume = {31},
 year = {1983}
}

@article{cole1986deterministic,
  title={Deterministic coin tossing with applications to optimal parallel list ranking},
  author={Cole, Richard and Vishkin, Uzi},
  journal={Information and Control},
  volume={70},
  number={1},
  pages={32--53},
  year={1986},
  publisher={Academic Press}
}

@article{stone1975parallel,
  title={Parallel tridiagonal equation solvers},
  author={Stone, Harold S},
  journal={ACM Transactions on Mathematical Software (TOMS)},
  volume={1},
  number={4},
  pages={289--307},
  year={1975},
  publisher={ACM New York, NY, USA}
}

@inproceedings{10.1145/2612669.2612687,
author = {Shun, Julian and Blelloch, Guy E.},
title = {Phase-Concurrent Hash Tables for Determinism},
year = {2014},
isbn = {9781450328210},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2612669.2612687},
doi = {10.1145/2612669.2612687},
booktitle = {Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {96–107},
numpages = {12},
keywords = {hash table, applications, determinism},
location = {Prague, Czech Republic},
series = {SPAA ’14}
}
  
@article{anderson1991deterministic,
  title={Deterministic parallel list ranking},
  author={Anderson, Richard J and Miller, Gary L},
  journal={Algorithmica},
  volume={6},
  number={1-6},
  pages={859--868},
  year={1991},
  publisher={Springer}
}

@inproceedings{fortune1978parallelism,
  title={Parallelism in random access machines},
  author={Fortune, Steven and Wyllie, James},
  booktitle={Proceedings of the tenth annual ACM symposium on Theory of computing},
  pages={114--118},
  year={1978}
}

@article{doi:10.1137/0217026,
author = {Chazelle, Bernard},
title = {A Functional Approach to Data Structures and Its Use in Multidimensional Searching},
journal = {SIAM Journal on Computing},
volume = {17},
number = {3},
pages = {427-462},
year = {1988},
doi = {10.1137/0217026},
URL = { 
        https://doi.org/10.1137/0217026
},
eprint = { 
        https://doi.org/10.1137/0217026
}
}

@inproceedings{10.5555/3039686.3039811,
author = {Henzinger, Monika and Rao, Satish and Wang, Di},
title = {Local Flow Partitioning for Faster Edge Connectivity},
year = {2017},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {1919–1938},
numpages = {20},
location = {Barcelona, Spain},
series = {SODA ’17}
}
  
@inproceedings{10.5555/3381089.3381166,
author = {Ghaffari, Mohsen and Nowicki, Krzysztof and Thorup, Mikkel},
title = {Faster Algorithms for Edge Connectivity via Random 2-out Contractions},
year = {2020},
publisher = {Society for Industrial and Applied Mathematics},
address = {USA},
booktitle = {Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {1260–1279},
numpages = {20},
location = {Salt Lake City, Utah},
series = {SODA ’20}
}
  
@book{de2008computational,
  title={Computational Geometry: Algorithms and Applications},
  author={de Berg, Mark and Cheong, Otfried and van Kreveld, Marc and Overmars, Mark},
  year={2008},
  publisher={Springer Science \& Business Media}
}

@book{preparata2012computational,
  title={Computational geometry: an introduction},
  author={Preparata, Franco P and Shamos, Michael I},
  year={2012},
  publisher={Springer Science \& Business Media}
}

@article{doi:10.1137/0214019,
author = {Willard, Dan E.},
title = {New Data Structures for Orthogonal Range Queries},
journal = {SIAM Journal on Computing},
volume = {14},
number = {1},
pages = {232-253},
year = {1985},
doi = {10.1137/0214019},

URL = { 
        https://doi.org/10.1137/0214019
    
},
eprint = { 
        https://doi.org/10.1137/0214019
}
}

@inproceedings{10.1145/1998196.1998198,
author = {Chan, Timothy M. and Larsen, Kasper Green and P\u{a}tra\c{s}cu, Mihai},
title = {Orthogonal Range Searching on the RAM, Revisited},
year = {2011},
isbn = {9781450306829},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1998196.1998198},
doi = {10.1145/1998196.1998198},
booktitle = {Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry},
pages = {1–10},
numpages = {10},
keywords = {word RAM, dominance, geometric data structures, orthogonal range searching, maxima},
location = {Paris, France},
series = {SoCG ’11}
}
  
@inproceedings{sun2018pam,
  title={PAM: parallel augmented maps},
  author={Sun, Yihan and Ferizovic, Daniel and Belloch, Guy E},
  booktitle={Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming},
  pages={290--304},
  year={2018}
}

@INPROCEEDINGS{4568267,  
author={M. J. {Atallah} and R. {Cole} and M. T. {Goodrich}},  
booktitle={28th Annual Symposium on Foundations of Computer Science (sfcs 1987)},
title={Cascading divide-and-conquer: A technique for designing parallel algorithms},
year={1987},
volume={},
number={},
pages={151-160},
}

@article{aggarwal1988parallel,
  title={Parallel computational geometry},
  author={Aggarwal, Alok and Chazelle, Bernard and Guibas, Leo and {\'O}'D{\'u}nlaing, Colm and Yap, Chee},
  journal={Algorithmica},
  volume={3},
  number={1-4},
  pages={293--327},
  year={1988},
  publisher={Springer}
}

@article{afshani2019independent,
  title={Independent range sampling, revisited again},
  author={Afshani, Peyman and Phillips, Jeff M},
  journal={arXiv preprint arXiv:1903.08014},
  year={2019}
}

@inproceedings{afshani2017independent,
  title={Independent range sampling, revisited},
  author={Afshani, Peyman and Wei, Zhewei},
  booktitle={25th Annual European Symposium on Algorithms (ESA 2017)},
  year={2017},
  organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@inproceedings{hu2014independent,
  title={Independent range sampling},
  author={Hu, Xiaocheng and Qiao, Miao and Tao, Yufei},
  booktitle={Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems},
  pages={246--255},
  year={2014}
}

@article{BENTLEY1979244,
title = "Decomposable searching problems",
journal = "Information Processing Letters",
volume = "8",
number = "5",
pages = "244 - 251",
year = "1979",
issn = "0020-0190",
doi = "https://doi.org/10.1016/0020-0190(79)90117-0",
url = "http://www.sciencedirect.com/science/article/pii/0020019079901170",
author = "Jon Louis Bentley",
keywords = "Data structures, computational complexity, software engineering tools"
}

@incollection{ford2009maximal,
  title={Maximal flow through a network},
  author={Ford, Lester Randolph and Fulkerson, Delbert R},
  booktitle={Classic papers in combinatorics},
  pages={243--248},
  year={2009},
  publisher={Springer}
}

@article{gomory1961multi,
  title={Multi-terminal network flows},
  author={Gomory, Ralph E and Hu, Tien Chung},
  journal={Journal of the Society for Industrial and Applied Mathematics},
  volume={9},
  number={4},
  pages={551--570},
  year={1961},
  publisher={SIAM}
}

@article{gawrychowski2019minimum,
  title={Minimum Cut in $O(m/\log^2 n)$ Time},
  author={Gawrychowski, Pawel and Mozes, Shay and Weimann, Oren},
  journal={arXiv preprint arXiv:1911.01145},
  year={2019}
}

@article{walker1974new,
  title={New fast method for generating discrete random numbers with arbitrary frequency distributions},
  author={Walker, Alastair J},
  journal={Electronics Letters},
  volume={10},
  number={8},
  pages={127--128},
  year={1974},
  publisher={IET}
}

@inproceedings{atallah1986efficient,
  title={Efficient plane sweeping in parallel},
  author={Atallah, Mikhail J and Goodrich, Michael T},
  booktitle={Proceedings of the second annual symposium on Computational geometry},
  pages={216--225},
  year={1986}
}

@article{dory2020distributed,
  title={Distributed Weighted Min-Cut in Nearly-Optimal Time},
  author={Dory, Michal and Efron, Yuval and Mukhopadhyay, Sagnik and Nanongkai, Danupon},
  journal={arXiv preprint arXiv:2004.09129},
  year={2020}
}

@article{harel1984fast,
  title={Fast algorithms for finding nearest common ancestors},
  author={Harel, Dov and Tarjan, Robert Endre},
  journal={siam Journal on Computing},
  volume={13},
  number={2},
  pages={338--355},
  year={1984},
  publisher={SIAM}
}

@article{shiloach1982n2log,
  title={An O (n2log n) parallel max-flow algorithm},
  author={Shiloach, Yossi and Vishkin, Uzi},
  journal={Journal of Algorithms},
  volume={3},
  number={2},
  pages={128--146},
  year={1982},
  publisher={Elsevier}
}

@book{arora2009computational,
  title={Computational complexity: a modern approach},
  author={Arora, Sanjeev and Barak, Boaz},
  year={2009},
  publisher={Cambridge University Press}
}

@article{diestel2000graduate,
  title={Graduate texts in mathematics},
  author={Diestel, Reinhard},
  journal={Graph theory},
  volume={173},
  year={2000}
}

@book{harary1969graph,
  title={Graph Theory (on Demand Printing Of 02787)},
  author={Harary, F. and NATO Advanced Study Institute, Paris, 1963},
  lccn={69019989},
  series={Addison-Wesley series in mathematics},
  url={https://books.google.se/books?id=QNxgQZQH868C},
  year={1969},
  publisher={Avalon Publishing}
}

@book{stadtherr1998work,
  title={Work Efficient Parallel Scheduling Algorithms},
  author={Stadtherr, H.},
  isbn={9783896753069},
  url={https://books.google.se/books?id=IjtJ6QJavU4C},
  year={1998},
  publisher={Utz, Wiss.}
}

@book{wallis2010beginner,
  title={A Beginner's Guide to Graph Theory},
  author={Wallis, W.D.},
  isbn={9780817645809},
  lccn={2006936809},
  url={https://books.google.se/books?id=240QO32GJOcC},
  year={2010},
  publisher={Birkh{\"a}user Boston}
}

@book{rosen2012discrete,
  title={Discrete mathematics and its applications: with combinatorics and graph theory},
  author={Rosen, Kenneth H and Krithivasan, Kamala},
  year={2012},
  publisher={Tata McGraw-Hill Education}
}

@article{vishkin2007thinking,
  title={Thinking in parallel: Some basic data-parallel algorithms and techniques},
  author={Vishkin, Uzi}
}

@inproceedings{maggs1995models,
  title={Models of parallel computation: A survey and synthesis},
  author={Maggs, Bruce M and Matheson, Lesley R and Tarjan, Robert Endre},
  booktitle={Proceedings of the Twenty-Eighth Annual Hawaii International Conference on System Sciences},
  volume={2},
  pages={61--70},
  year={1995},
  organization={IEEE}
}

@article{kessler2007models,
  title={Models for parallel computing: Review and perspectives},
  author={Kessler, Christoph and Keller, J{\"o}rg},
  journal={Mitteilungen-Gesellschaft f{\"u}r Informatik eV, Parallel-Algorithmen und Rechnerstrukturen},
  volume={24},
  pages={13--29},
  year={2007}
}

@phdthesis{gu2018write,
  title={Write-efficient Algorithms},
  author={Gu, Yan},
  year={2018},
  school={Intel}
}

@article{karp1990parallel,
  title={Parallel algorithms for shared-memory machines},
  author={KARP, RM},
  journal={Handbook of Theoretical Computer Science},
  year={1990},
  publisher={Elsevier Science Publishers}
}

@article{cook1973time,
  title={Time bounded random access machines},
  author={Cook, Stephen A and Reckhow, Robert A},
  journal={Journal of Computer and System Sciences},
  volume={7},
  number={4},
  pages={354--375},
  year={1973},
  publisher={Elsevier}
}

@inproceedings{gibbons1989more,
  title={A more practical PRAM model},
  author={Gibbons, Phillip B},
  booktitle={Proceedings of the first annual ACM symposium on Parallel algorithms and architectures},
  pages={158--168},
  year={1989}
}

@book{wallis2013beginner,
  title={A Beginner's Guide to Graph Theory},
  author={Wallis, W.D.},
  isbn={9781475731347},
  lccn={00031172},
  url={https://books.google.se/books?id=affTBwAAQBAJ},
  year={2013},
  publisher={Birkh{\"a}user Boston}
}

@article{hagerup1989optimal,
  title={Optimal merging and sorting on the EREW PRAM},
  author={Hagerup, Torben and R{\"u}b, Christine},
  journal={Information Processing Letters},
  volume={33},
  number={4},
  pages={181--185},
  year={1989},
  publisher={Elsevier}
}

@article{anderson1989parallel,
  title={Parallel approximation algorithms for bin packing},
  author={Anderson, Richard J and Mayr, Ernst W and Warmuth, Manfred K},
  journal={Information and Computation},
  volume={82},
  number={3},
  pages={262--277},
  year={1989},
  publisher={Elsevier}
}

@book{knuth1998art,
  title={The art of computer programming: Volume 3: Sorting and Searching},
  author={Knuth, Donald E},
  year={1998},
  publisher={Addison-Wesley Professional}
}

@phdthesis{natvig1990evaluating,
  title={Evaluating Parallel Algorithms: Theoretical and Practical Aspects},
  author={Natvig, Lasse},
  year={1990},
  school={Citeseer}
}

@inproceedings{Natvig2002InvestigatingTP,
  title={Investigating the Practical Value of Cole's $O(\log N)$ Time CREW PRAM Merge Sort Algorithm},
  author={Lasse Natvig},
  booktitle={5th International Symposium on Computing and Information Sciences},
  year={1990}
}

@incollection{SCHMIDT201821,
title = "Chapter 2 - Theoretical Background",
editor = "Bertil Schmidt and Jorge González-Domínguez and Christian Hundt and Moritz Schlarb",
booktitle = "Parallel Programming",
publisher = "Morgan Kaufmann",
pages = "21 - 45",
year = "2018",
isbn = "978-0-12-849890-3",
doi = "https://doi.org/10.1016/B978-0-12-849890-3.00002-2",
url = "http://www.sciencedirect.com/science/article/pii/B9780128498903000022",
author = "Bertil Schmidt and Jorge González-Domínguez and Christian Hundt and Moritz Schlarb",
keywords = "PRAM, Parallel reduction, Prefix scan, Network topology, Degree, Diameter, Bisection-width, Linear array, Mesh, Binary tree, Hypercube, Amdahl's law, Gustafson's law, Strong scaling, Weak scaling, Scaled speedup, Iso-efficiency analysis, Foster's methodology, Parallel algorithm design, Jacobi iteration"
}

@article{schieber1988finding,
  title={On finding lowest common ancestors: Simplification and parallelization},
  author={Schieber, Baruch and Vishkin, Uzi},
  journal={SIAM Journal on Computing},
  volume={17},
  number={6},
  pages={1253--1262},
  year={1988},
  publisher={SIAM}
}

@article{nishimura1995efficient,
  title={Efficient asynchronous simulation of a class of synchronous parallel algorithms},
  author={Nishimura, Naomi},
  journal={Journal of Computer and System Sciences},
  volume={50},
  number={1},
  pages={98--113},
  year={1995},
  publisher={Elsevier}
}

@inproceedings{10.1145/1993636.1993647,
author = {Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya},
title = {A General Framework for Graph Sparsification},
year = {2011},
isbn = {9781450306911},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1993636.1993647},
doi = {10.1145/1993636.1993647},
booktitle = {Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing},
pages = {71–80},
numpages = {10},
keywords = {graph sparsification, edge connectivity, sampling},
location = {San Jose, California, USA},
series = {STOC ’11}
}
  
@inproceedings{benczur1996approximating,
  title={Approximating st minimum cuts in {\~O} (n 2) time},
  author={Bencz{\'u}r, Andr{\'a}s A and Karger, David R},
  booktitle={Proceedings of the twenty-eighth annual ACM symposium on Theory of computing},
  pages={47--55},
  year={1996}
}

@inproceedings{matula1993linear,
  title={A linear time 2+ $\varepsilon$ approximation algorithm for edge connectivity},
  author={Matula, David W},
  booktitle={Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms},
  pages={500--504},
  year={1993}
}

@article{eppstein1997sparsification,
  title={Sparsification—a technique for speeding up dynamic graph algorithms},
  author={Eppstein, David and Galil, Zvi and Italiano, Giuseppe F and Nissenzweig, Amnon},
  journal={Journal of the ACM (JACM)},
  volume={44},
  number={5},
  pages={669--696},
  year={1997},
  publisher={ACM New York, NY, USA}
}

@article{nagamochi1992linear,
  title={A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph},
  author={Nagamochi, Hiroshi and Ibaraki, Toshihide},
  journal={Algorithmica},
  volume={7},
  number={1-6},
  pages={583--596},
  year={1992},
  publisher={Springer}
}

@article{nagamochi1992computing,
  title={Computing edge-connectivity in multigraphs and capacitated graphs},
  author={Nagamochi, Hiroshi and Ibaraki, Toshihide},
  journal={SIAM Journal on Discrete Mathematics},
  volume={5},
  number={1},
  pages={54--66},
  year={1992},
  publisher={SIAM}
}

@article{cheriyan1993scan,
  title={Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity},
  author={Cheriyan, Joseph and Kao, Ming-Yang and Thurimella, Ramakrishna},
  journal={SIAM Journal on Computing},
  volume={22},
  number={1},
  pages={157--174},
  year={1993},
  publisher={SIAM}
}

@article{karger1995randomized,
  title={A randomized linear-time algorithm to find minimum spanning trees},
  author={Karger, David R and Klein, Philip N and Tarjan, Robert E},
  journal={Journal of the ACM (JACM)},
  volume={42},
  number={2},
  pages={321--328},
  year={1995},
  publisher={ACM New York, NY, USA}
}

@article{pettie2002randomized,
  title={A randomized time-work optimal parallel algorithm for finding a minimum spanning forest},
  author={Pettie, Seth and Ramachandran, Vijaya},
  journal={SIAM Journal on Computing},
  volume={31},
  number={6},
  pages={1879--1895},
  year={2002},
  publisher={SIAM}
}

@book{ahodesign,
  title={The design and analysis of computer algorithms},
  author={Aho, Alfred V and Hopcroft, John E},
  year={1974},
  publisher={Pearson Education India}
}

@article{agarwal1999geometric,
  title={Geometric range searching and its relatives},
  author={Agarwal, Pankaj K and Erickson, Jeff and others},
  journal={Contemporary Mathematics},
  volume={223},
  pages={1--56},
  year={1999}
}

@article{HALPERIN20011,
title = "Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests",
journal = "Journal of Algorithms",
volume = "39",
number = "1",
pages = "1 - 46",
year = "2001",
issn = "0196-6774",
doi = "https://doi.org/10.1006/jagm.2000.1146",
url = "http://www.sciencedirect.com/science/article/pii/S0196677400911465",
author = "Shay Halperin and Uri Zwick",
abstract = "We present the first randomized O(logn) time and O(m+n) work EREW PRAM algorithm for finding a spanning forest of an undirected graph G=(V,E) with n vertices and m edges. Our algorithm is optimal with respect to time, work, and space. As a consequence we get optimal randomized EREW PRAM algorithms for other basic connectivity problems such as finding a bipartite partition, finding bridges and biconnected components, finding Euler tours in Eulerian graphs, finding an ear decomposition, finding an open ear decomposition, finding a strong orientation, and finding an st-numbering."
}

@book{thulasiraman2016handbook,
  title={Handbook of Graph Theory, Combinatorial Optimization, and Algorithms},
  author={Thulasiraman, K.K.T. and Arumugam, S. and Brandst{\"a}dt, A. and Nishizeki, T.},
  isbn={9781420011074},
  lccn={2015021972},
  series={Chapman \& Hall/CRC Computer and Information Science Series},
  url={https://books.google.se/books?id=H\_IYCwAAQBAJ},
  year={2016},
  publisher={CRC Press}
}

@book{cormen2009introduction,
  title={Introduction to algorithms},
  author={Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford},
  year={2009},
  publisher={MIT press}
}

@inproceedings{cole1986approximate,
  title={Approximate and exact parallel scheduling with applications to list, tree and graph problems},
  author={Cole, Richard and Vishkin, Uzi},
  booktitle={27th Annual Symposium on Foundations of Computer Science (sfcs 1986)},
  pages={478--491},
  year={1986},
  organization={IEEE}
}

@article{gazit1991optimal,
  title={An optimal randomized parallel algorithm for finding connected components in a graph},
  author={Gazit, Hillel},
  journal={SIAM Journal on Computing},
  volume={20},
  number={6},
  pages={1046--1067},
  year={1991},
  publisher={SIAM}
}

@misc{knuth1976complexity,
  title={The complexity of nonuniform random number generation. Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), 357--428},
  author={Knuth, Donald E and Yao, Andrew C},
  year={1976},
  publisher={Academic Press, New York}
}

@book{storer2012introduction,
  title={An introduction to data structures and algorithms},
  author={Storer, James Andrew},
  year={2012},
  pages = {1-57},
  publisher={Springer Science \& Business Media}
}

@book{fishman2013discrete,
  title={Discrete-event simulation: modeling, programming, and analysis},
  author={Fishman, George S},
  year={2013},
  publisher={Springer Science \& Business Media}
}

@article{fishman1979sampling,
  title={Sampling from the binomial distribution on a computer},
  author={Fishman, George S},
  journal={Journal of the American Statistical Association},
  volume={74},
  number={366a},
  pages={418--423},
  year={1979},
  publisher={Taylor \& Francis}
}

@article{farach2015exact,
  title={Exact sublinear binomial sampling},
  author={Farach-Colton, Mart{\'i}n and Tsai, Meng-Tsung},
  journal={Algorithmica},
  volume={73},
  number={4},
  pages={637--651},
  year={2015},
  publisher={Springer}
}

@inproceedings{thorup2000dynamic,
  title={Dynamic graph algorithms with applications},
  author={Thorup, Mikkel and Karger, David R},
  booktitle={Scandinavian Workshop on Algorithm Theory},
  pages={1--9},
  year={2000},
  organization={Springer}
}

@inproceedings{neal1995randomized,
  title={Randomized rounding without solving the linear program},
  author={Young, Neal E},
  booktitle={Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms},
  volume={76},
  pages={170},
  year={1995},
  organization={SIAM}
}

@article{plotkin1995fast,
  title={Fast approximation algorithms for fractional packing and covering problems},
  author={Plotkin, Serge A and Shmoys, David B and Tardos, {\'E}va},
  journal={Mathematics of Operations Research},
  volume={20},
  number={2},
  pages={257--301},
  year={1995},
  publisher={INFORMS}
}

@article{nash1961edge,
  title={Edge-disjoint spanning trees of finite graphs},
  author={Nash-Williams, CSJA},
  journal={Journal of the London Mathematical Society},
  volume={1},
  number={1},
  pages={445--450},
  year={1961},
  publisher={Narnia}
}

@article{gabow1992forests,
  title={Forests, frames, and games: algorithms for matroid sums and applications},
  author={Gabow, Harold N and Westermann, Herbert H},
  journal={Algorithmica},
  volume={7},
  number={1-6},
  pages={465},
  year={1992},
  publisher={Springer}
}

@article{karger1997nc,
  title={An $\backslash$NC Algorithm for Minimum Cuts},
  author={Karger, David R and Motwani, Rajeev},
  journal={SIAM Journal on Computing},
  volume={26},
  number={1},
  pages={255--272},
  year={1997},
  publisher={SIAM}
}

@article{nagamochi2001efficient,
  title={An efficient NC algorithm for a sparse k-edge-connectivity certificate},
  author={Nagamochi, Hiroshi and Hasunuma, Toru},
  journal={Journal of Algorithms},
  volume={38},
  number={2},
  pages={354--373},
  year={2001},
  publisher={Elsevier}
}

@phdthesis{10.5555/915826,
author = {Thurimella, Ramakrishna and Fussell, Donald S.},
title = {Techniques for the Design of Parallel Graph Algorithms},
year = {1989},
publisher = {The University of Texas at Austin}
}

@inproceedings{paul1983parallel,
  title={Parallel dictionaries on 2--3 trees},
  author={Paul, Wolfgang and Vishkin, Uzi and Wagener, Hubert},
  booktitle={International Colloquium on Automata, Languages, and Programming},
  pages={597--609},
  year={1983},
  organization={Springer, Berlin, Heidelberg}
}

@article{Henzinger2018Practical,
             AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian and Strash, Darren},
             TITLE = {{Practical Minimum Cut Algorithms}},
             JOURNAL={Journal of Experimental Algorithmics (JEA)},
             VOLUME={23},
             NUMBER={1},
             PAGES={1--8},
             YEAR = {2018},
             PUBLISHER={ACM},
}

@inproceedings{henzinger2019shared,
             AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},
             TITLE = {{Shared-memory Exact Minimum Cuts}},
             BOOKTITLE = {2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
             PAGES = {13--22},
             ORGANIZATION = {IEEE},
             YEAR = {2019}
}

@article{gianinazzi2018communication,
  title={Communication-avoiding parallel minimum cuts and connected components},
  author={Gianinazzi, Lukas and Kalvoda, Pavel and De Palma, Alessandro and Besta, Maciej and Hoefler, Torsten},
  journal={ACM SIGPLAN Notices},
  volume={53},
  number={1},
  pages={219--232},
  year={2018},
  publisher={ACM New York, NY, USA}
}

@misc{gawrychowski2020note,
    title={A Note on a Recent Algorithm for Minimum Cut},
    author={Paweł Gawrychowski and Shay Mozes and Oren Weimann},
    year={2020},
    eprint={2008.02060},
    archivePrefix={arXiv},
    primaryClass={cs.DS}
}

@article{KAMBATLA20142561,
title = "Trends in big data analytics",
journal = "Journal of Parallel and Distributed Computing",
volume = "74",
number = "7",
pages = "2561 - 2573",
year = "2014",
note = "Special Issue on Perspectives on Parallel and Distributed Processing",
issn = "0743-7315",
doi = "https://doi.org/10.1016/j.jpdc.2014.01.003",
url = "http://www.sciencedirect.com/science/article/pii/S0743731514000057",
author = "Karthik Kambatla and Giorgos Kollias and Vipin Kumar and Ananth Grama",
}
main.bbl
\begin{thebibliography}{AKPS90}

\bibitem[AB21]{AndersonB2021}
Daniel Anderson and Guy~E. Blelloch.
\newblock Parallel minimum cuts in o(m log2 (n)) work and low depth.
\newblock {\em CoRR}, abs/2102.05301, 2021.

\bibitem[AKPS90]{10.1145/97444.97693}
A.~Aggarwal, D.~Kravets, J.~Park, and S.~Sen.
\newblock Parallel searching in generalized monge arrays with applications.
\newblock In {\em Proceedings of the Second Annual ACM Symposium on Parallel
  Algorithms and Architectures}, SPAA '90, page 259–268, New York, NY, USA,
  1990. Association for Computing Machinery.

\bibitem[Ben79]{BENTLEY1979244}
Jon~Louis Bentley.
\newblock Decomposable searching problems.
\newblock {\em Information Processing Letters}, 8(5):244 -- 251, 1979.

\bibitem[Ble96]{GuyEBlelloch}
Guy~E. Blelloch.
\newblock Programming parallel algorithms.
\newblock {\em Commun. ACM}, 39:85--97, 03 1996.

\bibitem[BLS20]{bhardwaj_et_al:LIPIcs:2020:12259}
Nalin Bhardwaj, Antonio J.~Molina Lovett, and Bryce Sandlund.
\newblock {A Simple Algorithm for Minimum Cuts in Near-Linear Time}.
\newblock In {\em 17th Scandinavian Symposium and Workshops on Algorithm Theory
  (SWAT 2020)}. Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik, 2020.

\bibitem[Bre74]{10.1145/321812.321815}
Richard~P. Brent.
\newblock The parallel evaluation of general arithmetic expressions.
\newblock {\em J. ACM}, 21(2):201–206, April 1974.

\bibitem[CLRS09]{cormen2009introduction}
Thomas~H Cormen, Charles~E Leiserson, Ronald~L Rivest, and Clifford Stein.
\newblock {\em Introduction to algorithms}.
\newblock MIT press, 2009.

\bibitem[Fis79]{fishman1979sampling}
George~S Fishman.
\newblock Sampling from the binomial distribution on a computer.
\newblock {\em Journal of the American Statistical Association},
  74(366a):418--423, 1979.

\bibitem[Fis13]{fishman2013discrete}
George~S Fishman.
\newblock {\em Discrete-event simulation: modeling, programming, and analysis}.
\newblock Springer Science \& Business Media, 2013.

\bibitem[GG18]{10.1145/3210377.3210393}
Barbara Geissmann and Lukas Gianinazzi.
\newblock Parallel minimum cuts in near-linear work and low depth.
\newblock In {\em Proceedings of the 30th ACM Symposium on Parallelism in
  Algorithms and Architectures}, SPAA ’18, page 1–11, New York, NY, USA,
  2018. Association for Computing Machinery.

\bibitem[GMW19]{gawrychowski2019minimum}
Pawel Gawrychowski, Shay Mozes, and Oren Weimann.
\newblock Minimum cut in $o(m/\log^2 n)$ time.
\newblock {\em arXiv preprint arXiv:1911.01145}, 2019.

\bibitem[GMW20]{gawrychowski2020note}
Paweł Gawrychowski, Shay Mozes, and Oren Weimann.
\newblock A note on a recent algorithm for minimum cut, 2020.

\bibitem[GMW21]{gawrychowski2021note}
Pawe{\l} Gawrychowski, Shay Mozes, and Oren Weimann.
\newblock A note on a recent algorithm for minimum cut.
\newblock In {\em Symposium on Simplicity in Algorithms (SOSA)}, pages 74--79.
  SIAM, 2021.

\bibitem[GNT20]{GhaffariNT20}
Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup.
\newblock Faster algorithms for edge connectivity via random 2-out
  contractions.
\newblock In {\em {SODA}}. {SIAM}, 2020.

\bibitem[HRW17]{HenzingerRW17}
Monika Henzinger, Satish Rao, and Di~Wang.
\newblock Local flow partitioning for faster edge connectivity.
\newblock In {\em {SODA}}, pages 1919--1938. {SIAM}, 2017.

\bibitem[HZ01]{HALPERIN20011}
Shay Halperin and Uri Zwick.
\newblock Optimal randomized erew pram algorithms for finding spanning forests.
\newblock {\em Journal of Algorithms}, 39(1):1 -- 46, 2001.

\bibitem[J\'92]{10.5555/133889}
Joseph J\'{a}J\'{a}.
\newblock {\em An Introduction to Parallel Algorithms}.
\newblock Addison Wesley Longman Publishing Co., Inc., USA, 1992.

\bibitem[Kar94]{Karger:Thesis}
David~R. Karger.
\newblock {\em Random Sampling in Graph Optimization Problems}.
\newblock PhD thesis, Stanford University, Stanford, CA 94305, 1994.

\bibitem[Kar99]{10.2307/3690490}
David~R. Karger.
\newblock Random sampling in cut, flow, and network design problems.
\newblock {\em Mathematics of Operations Research}, 24(2):383--413, 1999.

\bibitem[Kar00]{Kar00}
David~R. Karger.
\newblock Minimum cuts in near-linear time.
\newblock {\em J. {ACM}}, 47(1):46--76, 2000.
\newblock announced at STOC'96.

\bibitem[KS88]{KachitvichyanukulS88}
Voratas Kachitvichyanukul and Bruce~W. Schmeiser.
\newblock Binomial random variate generation.
\newblock {\em Commun. ACM}, 31(2):216–222, February 1988.

\bibitem[LM20]{LopezMartinez1512083}
Andr\'es López~Martínez.
\newblock Parallel minimum cuts : An improved crew pram algorithm.
\newblock Master's thesis, KTH, School of Electrical Engineering and Computer
  Science (EECS), 2020.

\bibitem[Mat93]{matula1993linear}
David~W Matula.
\newblock A linear time 2+ $\varepsilon$ approximation algorithm for edge
  connectivity.
\newblock In {\em Proceedings of the fourth annual ACM-SIAM Symposium on
  Discrete algorithms}, pages 500--504, 1993.

\bibitem[MN20]{mukhopadhyay2019weighted}
Sagnik Mukhopadhyay and Danupon Nanongkai.
\newblock Weighted min-cut: Sequential, cut-query, and streaming algorithms.
\newblock In {\em Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory
  of Computing}, STOC 2020, page 496–509, New York, NY, USA, 2020.
  Association for Computing Machinery.

\bibitem[NI92a]{nagamochi1992computing}
Hiroshi Nagamochi and Toshihide Ibaraki.
\newblock Computing edge-connectivity in multigraphs and capacitated graphs.
\newblock {\em SIAM Journal on Discrete Mathematics}, 5(1):54--66, 1992.

\bibitem[NI92b]{nagamochi1992linear}
Hiroshi Nagamochi and Toshihide Ibaraki.
\newblock A linear-time algorithm for finding a sparsek-connected spanning
  subgraph of ak-connected graph.
\newblock {\em Algorithmica}, 7(1-6):583--596, 1992.

\bibitem[PR02]{pettie2002randomized}
Seth Pettie and Vijaya Ramachandran.
\newblock A randomized time-work optimal parallel algorithm for finding a
  minimum spanning forest.
\newblock {\em SIAM Journal on Computing}, 31(6):1879--1895, 2002.

\bibitem[PST95]{plotkin1995fast}
Serge~A Plotkin, David~B Shmoys, and {\'E}va Tardos.
\newblock Fast approximation algorithms for fractional packing and covering
  problems.
\newblock {\em Mathematics of Operations Research}, 20(2):257--301, 1995.

\bibitem[RV94]{10.5555/314464.314661}
Rajeev Raman and Uzi Vishkin.
\newblock Optimal randomized parallel algorithms for computing the row maxima
  of a totally monotone matrix.
\newblock In {\em Proceedings of the Fifth Annual ACM-SIAM Symposium on
  Discrete Algorithms}, SODA '94, page 613–621, USA, 1994. Society for
  Industrial and Applied Mathematics.

\bibitem[ST83]{SLEATOR1983362}
Daniel~D. Sleator and Robert~Endre Tarjan.
\newblock A data structure for dynamic trees.
\newblock {\em Journal of Computer and System Sciences}, 26(3):362 -- 391,
  1983.

\bibitem[SV82]{shiloach1982n2log}
Yossi Shiloach and Uzi Vishkin.
\newblock An o (n2log n) parallel max-flow algorithm.
\newblock {\em Journal of Algorithms}, 3(2):128--146, 1982.

\bibitem[TK00]{thorup2000dynamic}
Mikkel Thorup and David~R Karger.
\newblock Dynamic graph algorithms with applications.
\newblock In {\em Scandinavian Workshop on Algorithm Theory}, pages 1--9.
  Springer, 2000.

\bibitem[You95]{neal1995randomized}
Neal~E Young.
\newblock Randomized rounding without solving the linear program.
\newblock In {\em Proceedings of the sixth annual ACM-SIAM symposium on
  Discrete algorithms}, volume~76, page 170. SIAM, 1995.

\end{thebibliography}
