
\section{Introduction}
\input{intro.tex}

\section{Preliminaries}
\input{prelim.tex}

\section{Reduction to the $3$-edge-connected case}
\label{Smu1}
\input{reduction.tex}

\section{Simple randomized algorithm}
\input{randomized.tex}

\section{Deterministic algorithm}
\input{deterministic.tex}

\section{Reconstructing the structure of $4$-edge-connected components}
\label{Smu2}
\input{3cuttree.tex}

\section{Open problems}
\label{open-problems}
\input{open-problems.tex}

\bibliographystyle{abbrv}


\subsection{One tree edge}
\label{ssec:deterministic_1edge}

Recall that in this case, we are to find all $3$-edge-cuts intersecting a~fixed depth-first search tree ${\ensuremath{\mathcal{T}}}$ in a~single edge.
This is fairly straightforward: if some $3$-edge-cut $C$ contains exactly one tree edge $e$ of ${\ensuremath{\mathcal{T}}}$, then the border of the cut is exactly ${\ensuremath{\mathcal{T}}}_e$; hence, this cut must include all back edges leaping over $e$.
Therefore, $e$ belongs to a~$3$-edge-cut of this kind if and only if $\low[3](e) = \bot$, i.e. if there only exist two back edges leaping over $e$; in this case, $e$ and these two edges form a $3$-edge-cut.
Since this check can be easily performed in ${\ensuremath{\mathcal{O}}}(n)$ time for all tree edges in ${\ensuremath{\mathcal{T}}}$, the whole subroutine runs in ${\ensuremath{\mathcal{O}}}(n + m)$ time complexity.

\subsection{Two tree edges, lower case}
\label{ssec:deterministic_2edges_down}

Recall that this case requires us to find all $3$-edge-cuts intersecting a~fixed depth-first search tree ${\ensuremath{\mathcal{T}}}$ in two edges, say $e$ and $f$, such that $e < f$ and the remaining back edge $g$ connects ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ (Figure \ref{fig:randomized-two-tree-edge-cases}).
Hence, $g$ is the only back edge connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$, no back edges connect ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$, but there may be multiple back edges connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$.

We shall exploit the fact that in a~valid $3$-edge-cut of this kind, there are no back edges originating from ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ and leaping over $e$.
For a~fixed edge $e$, this severely limits the set of possible tree edges $f$ below $e$ in ${\ensuremath{\mathcal{T}}}$, since all back edges leaping over $e$ must originate from ${\ensuremath{\mathcal{T}}}_f$.
This is formalized by the notion of the \emph{deepest down cut} of~$e$:

\begin{definition}[deepest down cut]
  \label{def:deterministic_deepest_cut}
  For a~tree edge $e$ in ${\ensuremath{\mathcal{T}}}$, we define the \emph{deepest down cut} of~$e$, denoted $\DeepestDnCut(e)$, as the deepest tree edge $f \geq e$ for which all back edges leaping over $e$ originate from ${\ensuremath{\mathcal{T}}}_f$.
\end{definition}

\begin{lemma}
  \label{lem:deterministic_deepest_cut_def}
  For every tree edge $e$, $\DeepestDnCut(e)$ is defined correctly and uniquely. Moreover, every $3$-edge cut $\{e, f, g\}$ of the considered kind satisfies $e < f \leq \DeepestDnCut(e)$.
  \begin{proof}
    Let ${\ensuremath{\mathcal{S}}}_e$ be the set of the tails of all the edges leaping over~$e$.
    Then, $\DeepestDnCut(e)$ is the deepest tree edge $f=uv$ such that ${\ensuremath{\mathcal{S}}}_e \subseteq V({\ensuremath{\mathcal{T}}}_v)$.
    Equivalently, $v$ must be an ancestor of all the vertices in ${\ensuremath{\mathcal{S}}}_e$; hence, the deepest such vertex, the \emph{lowest common ancestor} of ${\ensuremath{\mathcal{S}}}_e$, is defined uniquely.
    The correctness of the definition of $\DeepestDnCut(e)$ follows.
    For the latter part of the lemma, observe that $f \leq \DeepestDnCut(e)$ if and only if every edge leaping over~$e$ originates from ${\ensuremath{\mathcal{T}}}_f$.
  \end{proof}
\end{lemma}

\begin{lemma}
  \label{lem:deterministic_deepest_cut_lca}
  For every tree edge $e$, $\DeepestDnCut(e) = uv$ is the tree edge whose head $v$ is the lowest common ancestor of two vertices: the tails of $\mindn[1](e)$ and $\maxdn[1](e)$.
  \begin{proof}
  Let ${\ensuremath{\mathcal{S}}}_e$ be the set defined in the proof of Lemma~\ref{lem:deterministic_deepest_cut_def}.
Then, $\DeepestDnCut(e) = uv$ is the tree edge whose head $v$ is the lowest common ancestor of ${\ensuremath{\mathcal{S}}}_e$.
  Equivalently, $v$ is the lowest common ancestor of two vertices: one of minimum preorder in ${\ensuremath{\mathcal{S}}}_e$, and the other of maximum preorder in ${\ensuremath{\mathcal{S}}}_e$.
  By definition, those two vertices are exactly the tails of $\mindn[1](e)$ and $\maxdn[1](e)$, respectively.
  \end{proof}
\end{lemma}

Thanks to Lemma~\ref{lem:deterministic_deepest_cut_lca}, we can compute $\DeepestDnCut(e)$ in constant time for each tree edge $e$ as the lowest common ancestor of two vertices can be computed in constant time after linear preprocessing~\cite{DBLP:journals/siamcomp/HarelT84}.

We now shift our focus to the lower tree edge $f$.
As in Section~\ref{sec:randomized_3cut}, the only possible candidate $g$ for a~back edge of the cut leaping over $f$ is given by $\maxup[1](f)$.
The only problematic part is locating the remaining tree edge $e$.
Previously, we utilized randomness in order to calculate the compressed hash of $e$ given the compressed hashes of $f$ and $g$.
Here, we instead use the following fact:

\begin{lemma}
  \label{lem:deterministic_deepest_edge_only}
  If $\{e, f, g\}$ is a~$3$-edge-cut of the considered kind for some tree edges $e$ and $f > e$, then $e$ is the deepest tree edge satisfying $\DeepestDnCut(e) \geq f$.
  \begin{proof}
    Naturally, the condition $\DeepestDnCut(e) \geq f$ must be satisfied if $\{e, f, g\}$ is a~$3$-edge-cut (Lemma~\ref{lem:deterministic_deepest_cut_def}).
    It only remains to prove that $e$ is the deepest edge with this property.
    Pick two tree edges $e_1$, $e_2$ such that $e_1 < e_2 < f$, both satisfying the condition regarding their deepest down cuts. We then partition the tree into four parts: ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_{e_1}$, ${\ensuremath{\mathcal{T}}}_{e_1} \setminus {\ensuremath{\mathcal{T}}}_{e_2}$, ${\ensuremath{\mathcal{T}}}_{e_2} \setminus {\ensuremath{\mathcal{T}}}_f$, and ${\ensuremath{\mathcal{T}}}_f$. By the assumptions, all back edges leaping over $e_1$ or over $e_2$ must originate from ${\ensuremath{\mathcal{T}}}_f$ (Figure~\ref{fig:deterministic_only_deepest_dn_cut}).

    Since $G$ is $3$-edge-connected, $\{e_2, f\}$ cannot be its edge cut; there must exist a~back edge $x_1$ connecting ${\ensuremath{\mathcal{T}}}_{e_2} \setminus {\ensuremath{\mathcal{T}}}_f$ with the rest of the graph.
    It cannot leap over $e_2$ as it would also need to originate from ${\ensuremath{\mathcal{T}}}_f$; hence, $x_1$ connects ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_{e_2} \setminus {\ensuremath{\mathcal{T}}}_f$.
    Analogously, $\{e_1, e_2\}$ is not an~edge cut of $G$, from which we infer that there exists another back edge $x_2$ connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_{e_1} \setminus {\ensuremath{\mathcal{T}}}_{e_2}$.
    Since we produced two separate back edges $x_1$, $x_2$ connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_{e_1} \setminus {\ensuremath{\mathcal{T}}}_f$, there cannot exist any $3$-edge-cut containing both $e_1$ and $f$.
    The statement of the lemma follows.
  \begin{figure}[h]
    \centering
    \includegraphics[scale=0.4]{figures/deterministic-only-deepest-dn-cut-inkscape.pdf}
    \caption{The setting in Lemma~\ref{lem:deterministic_deepest_edge_only}. Given that $\DeepestDnCut(e_1) \geq f$ and $\DeepestDnCut(e_2) \geq f$, the red back edges are forbidden from occurring in $G$, while the blue back edges can appear in $G$. We prove that both $x_1$ and $x_2$ appear in the graph.}
    \label{fig:deterministic_only_deepest_dn_cut}
  \end{figure}
  \end{proof}
\end{lemma}

Lemmas~\ref{lem:deterministic_deepest_cut_def} and~\ref{lem:deterministic_deepest_edge_only} naturally lead to the following idea: given a~tree edge $e$, the set of edges $f$ satisfying $\DeepestDnCut(e) \geq f$ is a~path $P_e$ connecting the head of $e$ with the head of $\DeepestDnCut(e)$; we assign this path a~weight $w_e$ equal to the depth of $e$ in~${\ensuremath{\mathcal{T}}}$.
We then invoke Theorem~\ref{thm:min_edge_path} with the tree ${\ensuremath{\mathcal{T}}}$, the weighted paths $\{P_e\,\mid\,e \in E({\ensuremath{\mathcal{T}}})\}$, and $k = 1$.
This allows us to find, in ${\ensuremath{\mathcal{O}}}(n)$ time, for each tree edge $f \in E({\ensuremath{\mathcal{T}}})$, the path $P_e$ of the maximum weight containing $f$ as an~edge.
This path naturally corresponds to the tree edge~$e$ from Lemma~\ref{lem:deterministic_deepest_edge_only}.
This way, for every tree edge $f$, we have uniquely identified a~back edge $g$ and a~tree edge $e$ such that the only possible $3$-edge-cut containing $f$ as a~deeper tree edge, if it exists, is $\{e, f, g\}$.

It only remains to verify that $\{e, f, g\}$ is a $3$-edge-cut.
We need to make sure that:
\begin{itemize}
  \item All back edges leaping over $e$ originate from ${\ensuremath{\mathcal{T}}}_f$.
    The equivalent condition $\DeepestDnCut(e) \geq f$ is guaranteed by the algorithm, so we do not need to check it again.
  \item Exactly one edge ($g$) connects ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$.
    Since $g = \maxup[1](f)$, it suffices to verify that the edge $\maxup[2](f)$, which is a~back edge leaping over $f$ whose head is the deepest apart from $g$, also leaps over $e$ (i.e., it does not terminate in ${\ensuremath{\mathcal{T}}}_e$).
\end{itemize}



It can be easily verified that the implementation of the subroutine is deterministic and runs in linear time with respect to the size of $G$.

\subsection{Two tree edges, upper case}
\label{ssec:deterministic_2edges_up}

Recall that in this case, we are required to find all $3$-edge-cuts intersecting ${\ensuremath{\mathcal{T}}}$ in two edges $e$ and $f$, such that $e < f$ and the remaining back edge $g$ connects ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$ (Figure \ref{fig:randomized-two-tree-edge-cases}).
Similarly to the randomized case, we use the fact that given a~tree edge $e$, the tail of $g$ has either the smallest preorder (i.e., $g = \mindn[1](e)$) or the largest preorder (i.e., $g = \maxdn[1](e)$) among all the back edges leaping over $e$.
Without loss of generality, assume that $g = \mindn[1](e)$; the latter case is analogous.

In a~similar vein to previous case, observe that if $\{e, f, g\}$ is a~$3$-edge-cut for some $f > e$, then all back edges leaping over $e$ other than $g$ must originate from ${\ensuremath{\mathcal{T}}}_f$.

This leads to the following slight generalization of $\DeepestDnCut$ (Definition~\ref{def:deterministic_deepest_cut}):
\begin{definition}
  \label{def:deterministic_deepest_nomin_cut}
  For a~tree edge $e$ in ${\ensuremath{\mathcal{T}}}$, we define the value $\DeepestDnCutNoMin(e)$ as the deepest tree edge $f \geq e$ for which all back edges leaping over $e$ other than $\mindn[1](e)$ originate from ${\ensuremath{\mathcal{T}}}_f$.
\end{definition}
The process of computation of $\DeepestDnCut(e)$ asserted by Lemma~\ref{lem:deterministic_deepest_cut_lca} can be easily modified to match our needs: recall that $\DeepestDnCut(e)$ is the tree edge whose head was the lowest common ancestor of the origins of $\mindn[1](e)$ and $\maxdn[1](e)$.
Since we exclude $\mindn[1](e)$ from the condition in Definition~\ref{def:deterministic_deepest_nomin_cut}, we use the edge $\mindn[2](e)$ instead: that is, the back edge leaping over $e$, with the next lowest preorder of the tail.
Therefore, we compute $\DeepestDnCutNoMin(e)$ as the tree edge whose head is the lowest common ancestor of the tails of $\mindn[2](e)$ and $\maxdn[1](e)$ (Figure~\ref{fig:deterministic_upcase_f0}).

\begin{figure}[h]
\centering
  \includegraphics[scale=0.4]{figures/deterministic-upcase-dncut-inkscape.pdf}
\caption{The computation of $f_0 = \DeepestDnCutNoMin(e)$ excludes $g = \mindn[1](e)$, and computes the lowest common ancestor of the remaining back edges leaping over $e$.}
\label{fig:deterministic_upcase_f0}
\end{figure}

Now, fix the shallower tree edge $e$ of the cut.
Let $f_0 := \DeepestDnCutNoMin(e)$.
Then, if some tree edge $f > e$ belongs to the $3$-edge-cut $\{e, f, g\}$, then $f \leq f_0$ (otherwise, there would be multiple edges connecting ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$).
The natural question is then: is $\{e, f_0, g\}$ a~$3$-edge-cut?
The only possible problem is that there may exist back edges connecting ${\ensuremath{\mathcal{T}}}_{f_0}$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_{f_0}$.
Fortunately, if this is the case, then the back edge $\maxup1(f_0)$, dependent only on $f_0$, is one of these back edges.

Hence, let $h_0 := \maxup[1](f_0)$.
If $h_0$ leaps over $e$, we are done, and $\{e, f_0, g\}$ is an~edge cut.
Otherwise, the subtree ${\ensuremath{\mathcal{T}}}_f$ for the sought $3$-edge-cut $\{e, f, g\}$ must contain the head of $h_0$ (or else $h_0$ would connect ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$).
Let then $f_1$, $e \leq f_1 < f_0$ be the deepest tree edge containing the head of $h_0$, that is, the edge whose head coincides with the head of $h_0$.
Then, the edge $f$ of the $3$-edge-cut $\{e, f, g\}$ must satisfy $e < f \leq f_1$.
We can then repeat this procedure: given $f_1$, we compute $h_1 := \maxup[1](f_1)$, and either $h_1$ leaps over $e$ and we are done, or we calculate another edge $f_2 < f_1$ supplying a~better bound on the depth of $f$ (Figure~\ref{fig:deterministic_upcase_iter}).
Since the graph is finite, this process terminates in $k = {\ensuremath{\mathcal{O}}}(n)$ steps, producing the lowest tree edge $f_k \geq e$ such that no back edge connects ${\ensuremath{\mathcal{T}}}_{f_k}$ with ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_{f_k}$, and no back edge other than $g$ connects ${\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_{f_k}$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$.
If $f_k = e$, then no $3$-edge-cut $\{e, f, g\}$ exists for $f > e$.
Otherwise, $\{e, f_k, g\}$ is naturally a~correct $3$-edge-cut.
Since two edges of a $3$-edge-cut uniquely identify the third edge (Lemma~\ref{lem:randomized_unique_remaining_edge}), we conclude that this is the only $3$-edge-cut containing $e$ and $g$.

\begin{figure}[h]
\centering
  \includegraphics[scale=0.4]{figures/deterministic-upcase-iteration-inkscape.pdf}
\caption{The main iteration of the algorithm. We set $f_0 = \DeepestDnCutNoMin(e)$, $h_i = \maxup[1](f_i)$, and $f_{i+1}$ is the tree edge with the same head as $h_i$.}
\label{fig:deterministic_upcase_iter}
\end{figure}

We can now sum up the inefficient deterministic implementation of the algorithm for the current case (Algorithm~\ref{alg:deterministic_2edges_up_bad}).

\begin{algorithm}[H]
  \begin{algorithmic}
  \caption{Inefficient deterministic solution for ``two tree edges, upper case''}
  \label{alg:deterministic_2edges_up_bad}
  \Function {SolveTwoTreeEdgesUpper} {}
  \For{$e \in E({\ensuremath{\mathcal{T}}})$}
    \State $f_0 \gets \DeepestDnCutNoMin(e)$
    \State $g \gets \mindn[1](e)$
    \State $i \gets 0$
    \While {$f_i \neq e$ and $\maxup[1](e).\mathrm{head} \in {\ensuremath{\mathcal{T}}}_e$}
      \State $h_i \gets \maxup[1](e)$
      \State $f_{i+1} \gets$ the tree edge with the same head as $h_i$
      \State $i \gets i + 1$
    \EndWhile
    \If {$f_i \neq e$}
      \State add $\{e, f_i, g\}$ to the list of $3$-edge-cuts
    \EndIf
  \EndFor
  
  \Comment {{\small Run the analogous algorithm for $\DeepestDnCutNoMax$ instead of $\DeepestDnCutNoMin$}.}
  \EndFunction

  \end{algorithmic}
\end{algorithm}


In order to optimize the algorithm, we seek to eliminate the $\mathsf{while}$ loop.
Indeed, for each $e \in E({\ensuremath{\mathcal{T}}})$, the process is very similar: start with some edge $f > e$, and then repeatedly replace $f$ with a~higher edge, until a~replacement would result in an~edge closer to the root than $e$.
We can model this process with a~rooted tree ${\ensuremath{\mathcal{U}}}$ defined as~follows:
\begin{itemize}
  \item the vertices of ${\ensuremath{\mathcal{U}}}$ are the tree edges of ${\ensuremath{\mathcal{T}}}$, and $\bot$,
  \item $\bot$ is the root of ${\ensuremath{\mathcal{U}}}$,
  \item for a~non-root vertex $e$ of ${\ensuremath{\mathcal{U}}}$, its parent is the tree edge with the same head as $\maxup[1](e)$.
    If the head of $\maxup[1](e)$ coincides with the root of ${\ensuremath{\mathcal{T}}}$, then the parent of $e$ in ${\ensuremath{\mathcal{U}}}$ is $\bot$.
\end{itemize}
Naturally, ${\ensuremath{\mathcal{U}}}$ can be constructed in linear time with respect to the size of ${\ensuremath{\mathcal{T}}}$; moreover, if an~edge $p$ is a~parent of another edge $q$ in ${\ensuremath{\mathcal{U}}}$, then $p <_{\ensuremath{\mathcal{T}}} q$.

Now, the $\mathsf{while}$ loop is equivalent to repeated replacement of $f_0$ with its parent in ${\ensuremath{\mathcal{U}}}$ as long as the parent is greater or equal than $e$ with respect to $<_{\ensuremath{\mathcal{T}}}$.
In other words, the final edge $f' := \mathsf{final}(f_0, e)$ is taken as the shallowest ancestor of $f_0$ in ${\ensuremath{\mathcal{U}}}$ for which $f' \geq_{\ensuremath{\mathcal{T}}} e$.

This leads to the final idea: we simulate a~forest of rooted subtrees of ${\ensuremath{\mathcal{U}}}$ using a~disjoint set union data structure $F_{\ensuremath{\mathcal{U}}}$ (Theorem~\ref{thm:linear_fu}).
Each subtree additionally keeps its root, which can be retrieved from $F_{\ensuremath{\mathcal{U}}}$ (Lemma~\ref{enrich-parent}).
Initially, each subtree of ${\ensuremath{\mathcal{U}}}$ contains a~single vertex.

After the initialization of $F_{\ensuremath{\mathcal{U}}}$, we iterate $e$ over the tree edges of ${\ensuremath{\mathcal{T}}}$ in the decreasing order of depth in ${\ensuremath{\mathcal{T}}}$.
Throughout the process, we maintain the following invariant on $F_{\ensuremath{\mathcal{U}}}$: an edge $ef \in E({\ensuremath{\mathcal{U}}})$ for $e < f$ has been added to the forest if and only if $e$ has been considered at any previous iteration of the main loop.
Hence, at the beginning of the iteration for a~given edge $e$, we add to $F_{\ensuremath{\mathcal{U}}}$ all tree edges of ${\ensuremath{\mathcal{U}}}$ originating from $e$.
At this point of time, for every tree edge $f$ such that $f >_{\ensuremath{\mathcal{T}}} e$, the edge $\mathsf{final}(f, e)$ is given by $F_{\ensuremath{\mathcal{U}}}.\mathsf{lowest}(f)$.
This reduces the entire $\mathsf{while}$ loop to a~single $\mathsf{lowest}$ query on $F_{\ensuremath{\mathcal{U}}}$ (Algorithm~\ref{alg:deterministic_2edges_up_good}).
\begin{algorithm}[H]
  \begin{algorithmic}
  \caption{Efficient deterministic solution for ``two tree edges, upper case''}
  \label{alg:deterministic_2edges_up_good}
  \Function {SolveTwoTreeEdgesUpper} {}
  \State ${\ensuremath{\mathcal{U}}} \gets$ the rooted tree on $E({\ensuremath{\mathcal{T}}}) \cup \{\bot\}$ defined above
  \State $F_{\ensuremath{\mathcal{U}}} \gets$ the disjoint set union data structure built on ${\ensuremath{\mathcal{U}}}$ (Lemma~\ref{lem:linear_fu_with_lowest})
  \For{$e \in E({\ensuremath{\mathcal{T}}})$, in order from the deepest to the shallowest}
    \For{$c$ -- child of $e$ in ${\ensuremath{\mathcal{U}}}$}
      \State $F_{\ensuremath{\mathcal{U}}}.\mathsf{union}(e, c)$
    \EndFor
    \State $g \gets \mindn[1](e)$
    \State $f_0 \gets \DeepestDnCutNoMin(e)$
    \State $f' \gets F_{\ensuremath{\mathcal{U}}}.\mathsf{lowest}(f_0)$
    \If {$f' \neq e$}
      \State add $\{e, f', g\}$ to the list of $3$-edge-cuts
    \EndIf
  \EndFor

  \Comment {{\small Run the analogous algorithm for $\DeepestDnCutNoMax$ instead of $\DeepestDnCutNoMin$}.}
  \EndFunction

  \end{algorithmic}
\end{algorithm}


It can be easily seen that we initialize $F_{\ensuremath{\mathcal{U}}}$ on a~tree with $n$ vertices, and we issue ${\ensuremath{\mathcal{O}}}(n)$ queries to it in total.
Therefore, the whole subroutine runs in time linear with respect to the size of $G$.

Summing up, we replaced each randomized subroutine with its deterministic counterpart, preserving the linear guarantee on the runtime of the algorithm.
We conclude that there exists a deterministic linear-time algorithm listing $3$-edge-cuts in $3$-edge-connected graphs.
\subsection{Previous work}

There has been a~plethora of research into the algorithms deciding the $k$-vertex- and $k$-edge-connectedness of graphs, and decomposing the graphs into $k$-vertex- or $k$-edge-connected components.
However, while classical, elementary, and efficient algorithms exist for $k = 1$ and $k = 2$, these problems become increasingly more difficult for the larger values of $k$.
In fact, even for $k = 4$, there were no known linear time algorithms to any of the considered problems.
The following description presents the previous work in this area for $k \in \{1, 2, 3, 4\}$, and exhibits the related work for the larger values of $k$:

\paragraph{$\mathbf{k = 1}$.}
Here, the notions of $k$-vertex-connectedness and $k$-edge-connectedness reduce to that of connectivity and the connected components of a~graph. In the static setting, determining the connected components in linear time is trivial.
As a~consequence, more focus is being laid on dynamic algorithms maintaining the connected components of graphs.
In the incremental setting, where the edges can only be added to the dynamic graph, the optimal solution is provided by disjoint-set data structures \cite{FU}, which solve the problem in the amortized ${\ensuremath{\mathcal{O}}}(\alpha(n))$ time per query, where $\alpha(n)$ denotes the inverse of the Ackermann's fast-growing function. The fully dynamic data structures are also considered
 \cite{Wulff, Sparsification, Cos2, Cos3, Cos4, ThorupDuzo, Cos6, DynConnWorst, Bridge, DynConnSODA17}.

\paragraph{$\mathbf{k = 2}$.}
One step further are the notions of 2-vertex-connectivity (biconnectivity)
and 2-edge-connectivity.
In the static setting, partitioning of a~graph into $2$-vertex-connected or $2$-edge-connected components are classical problems, both solved in linear time by exploiting the properties of the low function~\cite{2ConnStatic}.
The incremental versions of both problems are again solved optimally in the amortized ${\ensuremath{\mathcal{O}}}(\alpha(n))$ time per query \cite{Westbrook1992}.
Significant research has been done in the dynamic setting as well \cite{DBLP:conf/wads/PengSS19, ThorupDuzo, Sparsification, Bridge, Dyn3EConn, Henzinger1995, Dyn2ConnBack}.

\paragraph{$\mathbf{k = 3}$.} As a next step, we consider 3-vertex-connectivity (triconnectivity) and 3-edge-connectivity.
An~optimal, linear time algorithm detecting the $3$-vertex-connected components was first given by Hopcroft and Tarjan~\cite{TriConn}.
The first linear algorithm for $3$-edge-connectivity was discovered much later by Galil and Italiano~\cite{EdgeToVertex}, where they present a~linear time reduction from the $k$-edge-connectivity problem to $k$-vertex-connectivity for $k \geq 3$, showing that in the static setting, the former problem is the easier of the two.
This was later followed by a~series of works simplifying the solution for $3$-edge-connectivity~\cite{Tsin1, Tsin2, 3E1, Tsin3}.
The incremental setting \cite{3Incr, IncrSPQR} and the dynamic setting \cite{Dyn3EConn, Sparsification} were also considered.

We also mention that in the case of 3-vertex-connectivity, there exists a structure called SPQR-tree which succinctly captures the structure of 2-vertex-cuts in graphs~\cite{SPQR, IncrSPQR}.
Its edge-connectivity analogue also exists, but we defer its introduction to the general setting.


\paragraph{$\mathbf{k = 4}$.}
We move on to the problems of 4-vertex-connectivity and 4-edge-connectivity.
A~notable result by Kanevsky et al.~\cite{QuadConn} supports maintaining 4-vertex-connected components in incremental graphs, with an~optimal ${\ensuremath{\mathcal{O}}}(\alpha(n))$ amortized time per query. Their result also yields the solution for static graphs in ${\ensuremath{\mathcal{O}}}(m + n \alpha(n))$ time complexity.
By applying the result of Galil and Italiano~\cite{EdgeToVertex}, we derive a~static algorithm determining the $4$-edge-connected components in the same time complexity.
This algorithm is optimal for $m = \Omega(n \alpha(n))$.

Another result by Dinitz and Westbrook~\cite{Dinitz1998} supports maintaining the $4$-edge-connected components in the incremental setting. Their algorithm processes any sequence of queries in ${\ensuremath{\mathcal{O}}}(q + m + n \log n)$ time where $q$ is the number of queries, and $m$ is the total number of inserted edges to the graph.

However, it is striking that the fastest solutions for $4$-edge-connectivity and $4$-vertex-connectivity for static graphs were derived from the on-line algorithms working in the incremental setting.
In particular, no linear time algorithms for $k = 4$ were known before.


\paragraph{$\mathbf{k \geq 5}$.}
As a side note, we also present the current knowledge on the general problems of $k$-vertex-connectivity and $k$-edge-connectivity. A~series of results~\cite{Karger, DetMinCut, HenzingerCut, AnotherMinCut} show that it is possible to compute the minimum edge cut of a~graph (i.e., determine the edge-connectivity of a~graph) in near-linear time.
The previously mentioned work by Dinitz and Westbrook~\cite{Dinitz1998} maintains the $k$-edge-connected components of an~incremental graph which is assumed to already have been initialized with a~$(k-1)$-edge-connected graph.
The data structure answers any sequence of on-line queries in ${\ensuremath{\mathcal{O}}}(q + m + k^2 n \log{(n / k)})$ time, where $q$ is the number of queries, and $m$ is the number of edges in the initial graph.

Gomory and Hu \cite{GomoryHu} proved that for any weighted, undirected graph $G$ there exists a weighted, undirected tree $T$ on the same vertex set such that for any two vertices $s, t \in V(G)$, the value of the minimum $s$-$t$ edge cut in $T$ is equal to the value of the minimum $s$-$t$ edge cut in $G$.
Moreover, such a~tree can be constructed using $n-1$ invocations of the maximum flow algorithm.
In an interesting result by Hariharan et al.~\cite{PartialGomory-Hu}, the decomposition of any graph into $k$-edge-connected components is constructed in ${\ensuremath{\mathcal{O}}}((m + nk^3) \cdot \polylog(n))$ time, producing a~partial Gomory-Hu tree as its result.

Dinitz et el.~\cite{Cactus} showed that the set of all minimum edge cuts can be succinctly represented with a~\textit{cactus graph}. When the minimum edge cut is odd, this cactus simplifies to a tree (see \cite[Corollary 8]{SimplerCactus}). These results imply that if the size of the minimum cut is odd, then the number of minimum cuts is ${\ensuremath{\mathcal{O}}}(n)$ and if it is even, then the number of minimum cuts is ${\ensuremath{\mathcal{O}}}(n^2)$. The structure of $k$-vertex-cuts was also investigated \cite{Longhui}.



\subsection{Our results}
In this work, we present a linear time, deterministic algorithm partitioning static, undirected graphs into $4$-edge-connected components. Even though the area of the dynamic versions of the algorithms for $k$-edge-connectivity is still thriving, the progress in static variants appears to have plateaued. In particular, both subquadratic algorithms determining the $4$-edge-connected components \cite{QuadConn, Dinitz1998} originate from their dynamic incremental equivalents and are almost thirty years old, yet they did not achieve the optimal linear running time. Hence, our work
constitutes the first progress in the static setting of $4$-edge-connectivity in a~long time. As a~side result, our algorithm also produces the tree representation of $3$-edge-cuts as explained in~\cite{SimplerCactus}.


\subsection{Organization of the work}
The paper is organized as follows.
In Section~\ref{Smu1}, we show how to reduce the problem of determining $4$-edge-connected components to the problem of determining $4$-edge-connected components in $3$-edge-connected graphs.
In Section~\ref{sec:randomized_3cut}, we show a~linear time, randomized Monte Carlo algorithm for listing all 3-edge-cuts in 3-edge-connected graphs.
In Section \ref{sec:deterministic_3cut}, we show how to remove the dependency on the randomness in the algorithm from the previous section, producing a~linear time, deterministic algorithm listing all 3-edge-cuts in 3-edge-connected graphs.
Then, in Section \ref{Smu2}, we construct a tree of 3-edge-cuts in a~3-connected graph, given the list of all its 3-edge cuts. This tree is then used to determine the 4-edge-connected components of the graph. 
Finally, in Section \ref{open-problems}, we present open problems related to this work.






\subsection{Zero tree edges}\label{0t}
\label{ssec:randomized_0tree}
As ${\ensuremath{\mathcal{T}}}$ is a spanning connected subgraph, 3-edge-cuts not containing any tree edges simply do not exist.
\subsection{One tree edge}\label{1t}
\label{ssec:randomized_1tree}
Let $e$ be an edge of ${\ensuremath{\mathcal{T}}}$ that is the only tree edge of some 3-edge-cut. The two resulting connected components after the removal of such a cut are ${\ensuremath{\mathcal{T}}}_e$ and ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$ (we are slightly abusing the notation here; we actually mean that the connected components are the subgraphs induced by the vertex sets of ${\ensuremath{\mathcal{T}}}_e$ and ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$, respectively). Since $e$ is not a bridge, $\low(e)$ is well-defined and it connects ${\ensuremath{\mathcal{T}}}_e$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$, so it belongs to this cut as well. This uniquely determines the third edge of this cut as it has to be the unique edge whose hash is $H(e) \oplus H(\low(e))$.

In order to detect all such cuts, we iterate over all tree edges $e$ and for each of them we look up in $M$ whether there exists an edge whose compressed hash is $CH(e) \oplus CH(\low(e))$. If it exists and if it turns out to be a non-tree edge, then we call it $g$ and output the triple $\{e, \low(e), g\}$ as a 3-edge-cut.
\subsection{Two tree edges}\label{2t}

Let $e$ and $f$ be the edges of ${\ensuremath{\mathcal{T}}}$ that form a 3-edge-cut together with some back edge $g$.

\begin{lemma}
	The edges $e$ and $f$ are comparable with respect to $\le_{{\ensuremath{\mathcal{T}}}}$.
\end{lemma}
\begin{proof} Assume otherwise. Then ${\ensuremath{\mathcal{T}}}_e$ and ${\ensuremath{\mathcal{T}}}_f$ are disjoint, and $L \coloneqq {\ensuremath{\mathcal{T}}}_e \cup {\ensuremath{\mathcal{T}}}_f$ and $R \coloneqq {\ensuremath{\mathcal{T}}} \setminus L$ are two connected components resulting from the removal of the 3-edge-cut containing $e$ and $f$. However, $\low(e)$ and $\low(f)$ are well-defined different edges connecting $L$ and $R$, so any cut between $L$ and $R$ would need to contain $e, f, \low(e)$ and $\low(f)$ at the same time---a~contradiction. This proves that $e$ and $f$ are comparable.
	\end{proof}

Without loss of generality, assume that $e <_{\ensuremath{\mathcal{T}}} f$. Then, the two resulting connected components
 are $L \coloneqq {\ensuremath{\mathcal{T}}}_e \setminus {\ensuremath{\mathcal{T}}}_f$ and $R \coloneqq {\ensuremath{\mathcal{T}}} \setminus L$. The remaining back edge $g$ has to connect $L$ and $R$. We will distinguish two cases, differing in the location of the remaining back edge:
 \textit{two tree edges, lower case}, where $g$ connects $L$ with ${\ensuremath{\mathcal{T}}}_f$, and \textit{two tree edges, upper case}, where $g$ connects $L$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$.
 
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.4]{figures/randomized-two-tree-edges-cases.pdf}
	\caption{The settings in \ref{2tl} and \ref{2tu}. Cuts that we are looking for are formed by edges $\{e, f, g\}$ in both cases.}
	\label{fig:randomized-two-tree-edge-cases}
\end{figure} 
 
\subsubsection{Two tree edges, lower case}\label{2tl}
\label{ssec:randomized_2tree_lo}

Let $A$ be the set of back edges between ${\ensuremath{\mathcal{T}}}_f$ and ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_f$. It consists of the edge $g$, which connects $L$ with ${\ensuremath{\mathcal{T}}}_f$, and of several edges connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$. Let $B$ be the set of heads of edges from $A$ (we remind that back edges are directed towards the root $r$). All elements of $B$ lie on the path from $f$ to the root $r$, and the head of $g$ is the deepest element of $B$.

Based on this observation, we are going to use the data structure from Theorem \ref{thm:min_edge_path}. We initialize an instance of it with the tree ${\ensuremath{\mathcal{T}}}$, $k=1$, $C=2n$ and paths $\{P_e \ | \ e$ is a back edge$\}$, where for each non-tree edge $e=xy$, where $y$ is its head, we create one input path $P_e$ from $x$ to $y$, and we set $w_e \coloneqq 2n - {\rm pre}(y)$. This data structure lets us for each tree edge $f$ determine the back edge leaping over $f$ with the biggest value of preorder of its head. We call this edge $\maxup(f)$. This back edge is the only candidate for the edge $g$ for a~fixed edge $f$.

Hence, we can find all such cuts by firstly initializing the data structure, and then iterating over all tree edges $f$.
For each $f$, we take $g=\maxup(f)$. Knowing $f$ and $g$, we can look up in $M$ whether there exists an edge whose compressed hash is $CH(f) \oplus CH(g)$ (Lemma~\ref{lem:randomized_unique_remaining_edge}). If it exists and if it is a tree edge, then we call it $e$ and output the triple $\{e, f, g\}$ as a 3-edge-cut.


\subsubsection{Two tree edges, upper case}\label{2tu}
\label{ssec:randomized_2tree_hi}

Let $A$ be the set of non-tree edges between ${\ensuremath{\mathcal{T}}}_e$ and ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$. It consists of the back edge $g$, which connects $L$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$, and of several edges connecting ${\ensuremath{\mathcal{T}}}_f$ with ${\ensuremath{\mathcal{T}}} \setminus {\ensuremath{\mathcal{T}}}_e$. Let $B$ be the set of the tails of the edges from $A$.
Let $v \in L$ be the tail of $g$. As $v \notin {\ensuremath{\mathcal{T}}}_f$, either for all vertices $u \in {\ensuremath{\mathcal{T}}}_f$ it holds that ${\rm pre}(v) < {\rm pre}(u)$, or for all vertices $u \in {\ensuremath{\mathcal{T}}}_f$ it holds that ${\rm pre}(u) < {\rm pre}(v)$.
In the first case, $v$ is the vertex with the smallest preorder which is a~tail of some edge leaping over $e$; while in the second case $v$ is the analogous vertex with largest preorder.

Based on this observation, we are going to use the data structure from Theorem \ref{thm:min_edge_path} again.
We initialize one instance of it with the tree ${\ensuremath{\mathcal{T}}}$, $k=1$, $C=2n$ and the paths $\{P_e \,\mid\, e\text{ is a back edge}\}$, where for each back edge $e=xy$, we create one input path $P_e$ from $x$ to $y$, and set $w_e \coloneqq {\rm pre}(x)$.
We also initialize another instance of this data structure in the same way, with the only difference that we set $w_e \coloneqq 2n - {\rm pre}(x)$ instead.
The first instance lets us for each tree edge $e$ determine the edge $\mindn(e)$ leaping over $e$ with the smallest preorder of its tail; while the second instance determines the analogous edge $\maxdn(e)$, only with the largest preorder.
By our considerations above, if any~desired $\{e, f, g\}$ cut exists, then $g \in \{\mindn(e), \maxdn(e)\}$.

Hence, we can find all such cuts by firstly initializing both instances of the data structure. Then, we iterate over all tree edges $e$, and for each $e$ we check both candidates for $g$. If our hash table contains an~edge whose compressed hash is $CH(e) \oplus CH(g)$ and it is a tree edge, then we call it $f$ and output the triple $\{e, f, g\}$ as a 3-edge-cut.


\subsection{Three tree edges}\label{3t}
\label{ssec:randomized_3tree}

Solving this case in a way similar to the previous cases seems intractable. We consider this subsection, together with the time analysis following it, as one of the key ideas of this work.

In this case, we assume that no non-tree edges belong to the cut.
Therefore, we can contract all of them simultaneously and recursively list all 3-edge-cuts in the resulting graph.
Since 3-edge-cuts in the contracted graph exactly correspond to the 3-edge-cuts consisting solely of tree edges in the original graph, this reduction is sound.
The contraction is performed in ${\ensuremath{\mathcal{O}}}(n + m)$ time by identifying the vertices within the connected components of $G - E({\ensuremath{\mathcal{T}}})$. Let $G'$ be the graph after these contractions. Since $G$ is 3-edge-connected, $G'$ has to be 3-edge connected as well, so the assumption about the input graph being 3-edge-connected is preserved. We do not modify the value of $b$ in the subsequent recursive calls, even though the value of $m$ will decrease.

\subsection{Time analysis}
\label{ssec:randomized_time_analysis}
We will now compute the expected time complexity of our algorithm. The subroutines detecting the cuts with at most two tree edges clearly take expected linear time. The only nontrivial part of the time analysis is the recursion in Subsection \ref{3t}. Let $T(m)$ denote the maximum expected time our algorithm needs to solve any graph with at most $m$ edges.
Since our graph is 3-edge-connected, the degree of each vertex in $G$ is at least three, so $|E(G)| \ge \frac{3}{2} |V(G)| \ge \frac{3}{2} |E(G')| \Rightarrow |E(G')| \le \frac{2}{3} |E(G)|$. The bound on $T(m)$ follows:
$$T(m) \le {\ensuremath{\mathcal{O}}}(m) + T\left(\frac{2}{3}m\right).$$
The solution to this recurrence is $T(m) = {\ensuremath{\mathcal{O}}}(m)$, hence the whole algorithm runs in expected linear time.

\subsection{Correctness analysis}
In this subsection, we are going to prove that our algorithm works with sufficiently high probability. The only reason it can output wrong result comes from the compression of hashes---if we used their uncompressed version instead, the algorithm would clearly be correct.


The maximum number of queries to our hash table is linear in terms of $n$, which follows from a similar argument to the one presented in Subsection~\ref{ssec:randomized_time_analysis}.
Hence, there exists some absolute constant $c$ such that the number of queries is bounded by $cn$.
For each query with value $q$, and for each edge whose hash is not equal to the hash whose compressed version we ask about, there is $2^{-b}$ probability that compressed version of this hash is equal to $q$.
Hence, the probability that we ever get a~false positive is bounded from above by $cnm2^{-b}$.
If we never get a~false positive, then our algorithm returns the correct output. Since $b = \ceil{3 \log_2(m)}$ and $n \le m$, we infer that $cnm2^{-b} \le \frac{c}{m}$.
Therefore, our algorithm works correctly with probability at least $1 - \frac{c}{m}$.



\subsection{Removing hash tables}
\label{ssec:removing_hash_tables}
As mentioned earlier, there is a way to avoid using hash tables in our algorithm. Since the values of compressed hashes of edges are polynomial in $m$ (at most $2m^3$), we are able to sort them in ${\ensuremath{\mathcal{O}}}(m)$ time using the radix sort.
Now, instead of requiring a data structure that allows us to query the existence of an edge with a particular value of its compressed hash, we create an object representing such query, which we are going to answer in the future in an offline manner. After gathering all such objects, we may sort them together with edges, where as keys for comparisons we use values of compressed hashes for edges and values of required compressed hashes for queries. All the keys for comparisons are polynomial, so we are able to sort them together in ${\ensuremath{\mathcal{O}}}(m)$ time using the radix sort. After the sorting, we are able to easily answer all queries offline.

This concludes the description of the randomized variant of the algorithm.

