$\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$
are non-zero

Figure 5.6: Two different non-isomorphic sub-cases of a min-cut as in CASE-6.
Here a circle correspond to a vertex set. And an double arrow line between
them indicate that there are some edges which have an end point in each of the
vertex set.

Also, as per Lemma 3.6 we need
$\eta(v_{1}),\eta(v_{2}),\eta(v_{3}),\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$
and $\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow})$ at at least one node
to decide for a min-cut as given by CASE-6.

We will first work with the case in Fig. 5.6(a). Here,
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$. In this sub-case node
$v_{1}$ can make the decision based on $\mathcal{S}^{3}(v_{1})$. We will prove
that if such a min-cut exists then $v_{2},v_{3}\in\mathcal{S}^{3}(v_{1})$. We
demonstrate the different cases in Figure 5.7. The three different cases are
in terms of the intersection of the paths
$\rho(v_{1}),\rho(v_{2}),\rho(v_{3})$. In all the sub-cases demonstrated in
the Fig. 5.7 we can see that the branching number
$\mathcal{\xi}\left(v_{1}\right){v_{2}},\mathcal{\xi}\left(v_{1}\right){v_{3}}\leq
3$. Thus $v_{2},v_{3}\in\mathcal{S}^{3}(v_{1})$. Here, $v_{1}$ just need to
pick pairs of nodes $a,b\in\mathcal{S}^{3}(v_{1})$ such that
${a}^{\downarrow},{b}^{\downarrow},{v_{1}}^{\downarrow}$ are pair-wise
mutually disjoint and compare
$\eta(a),\eta(b),\eta(v_{1}),\gamma({a}^{\downarrow},{v_{1}}^{\downarrow})$
and $\gamma({b}^{\downarrow},{v_{1}}^{\downarrow})$ as per Lemma 3.6.

Figure 5.7: Illustrating different types of sub-cases. We demonstrate the
$3$-Sketch as per the node $v_{1}$. Solid black line denote the tree paths in
Sketch of $v_{1}$. Dashed line represent other paths in tree $\mathcal{T}$.
Edges in red are cut edges. The different sub-cases occur based on the
intersection of three paths $\rho(v_{1}),\rho(v_{2}),\rho(v_{3})$. In sub-case
(A),
$\operatorname{LCA}(v_{1},v_{3})=\operatorname{LCA}(v_{2},v_{3})\neq\operatorname{LCA}(v_{1},v_{2})$.
In sub-case (B),
$\operatorname{LCA}(v_{1},v_{2})=\operatorname{LCA}(v_{1},v_{3})\neq\operatorname{LCA}(v_{2},v_{3})$.
In sub-case (C),
$\operatorname{LCA}(v_{1},v_{2})=\operatorname{LCA}(v_{1},v_{3})=\operatorname{LCA}(v_{2},v_{3})$.

Now, we will take the case as mentioned in Fig. 5.6(b). By the same argument
as above we can say that $v_{1},v_{2}\in\mathcal{S}^{3}(v_{3})$ and
$v_{1},v_{3}\in\mathcal{S}^{3}(v_{2})$. In this case
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})\neq 0$ and
$\mathcal{S}^{3}(v_{1})$ does not have
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$ which is required to make
a decision about the said min-cut as per Lemma 3.6. Thus node $v_{1}$ cannot
make the required decision based on only $\mathcal{S}^{3}(v_{1})$.

Amidst, the above mentioned challenge, there is an easy way around. Each node
$v\in V$ downcasts $\mathcal{S}^{3}(v)$ (its 3-Sketch) to all nodes in
${v}^{\downarrow}$. Since 3-Sketch is of size $O(D\log n)$ thus this takes
$O(D^{2})$ rounds. After this step every node $u$ has $\mathcal{S}^{3}(v)\
\forall v\in\mathcal{A}\left(u\right)$. Now each node $u$ sends
$\mathcal{S}^{3}(a)\ \forall a\in\mathcal{A}\left(u\right)$ to its non-tree
neighbors. Since there are as many as $D$ such sketches thus this takes
$O(D^{2})$ time. Also, $\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow})>0$
thus we know that there is at least one node node
$v_{1}^{\prime}\in{v_{1}}^{\downarrow}$ and
$v_{2}^{\prime}\in{v_{2}}^{\downarrow}$ such that
$(v_{1}^{\prime},v_{2}^{\prime})$ is a non-tree edge. After the above
mentioned steps node $v_{1}^{\prime}$ as well as node $v_{2}^{\prime}$ will
have both $\mathcal{S}^{3}(v_{1})$ and $\mathcal{S}^{3}(v_{2})$. Now, both
${v_{1}^{\prime}}$ and ${v_{2}^{\prime}}$ can make the decision about the said
min-cut. We will discuss steps which may be undertaken at node
$v_{1}^{\prime}$ for the sane, for each
$v\in\mathcal{A}\left(v_{1}^{\prime}\right)$, $v_{1}^{\prime}$ locally
iterates through all the parallel paths of the $\mathcal{S}^{3}(v)$ and picks
all possible $x,y$ such that
${x}^{\downarrow},{y}^{\downarrow},{v}^{\downarrow}$ are mutually disjoint.
Notice that through $\mathcal{S}^{3}(v)$, $v_{1}^{\prime}$ has
$\gamma({x}^{\downarrow},{v}^{\downarrow}),\gamma({y}^{\downarrow},{v}^{\downarrow}),\eta(x),\eta(y)$.
Also it has $\eta(v)$ from previous calculations. Now from the sketches
received through its non-tree neighbors $v_{1}^{\prime}$ looks for
$\gamma({x}^{\downarrow},{y}^{\downarrow})$. If
$\gamma({x}^{\downarrow},{v}^{\downarrow}),\gamma({y}^{\downarrow},{v}^{\downarrow}),\eta(x),\eta(y)$
and $\gamma({x}^{\downarrow},{y}^{\downarrow})$ then satisfies Lemma 3.6 then
it can make the decision about the required min-cut. ∎

Next, we move to CASE-7. Here we will use reduced sketch as given in
Definition 5.11. First we the use the reduced $2$-sketch.

######  Observation 5.19.

For some $v_{1},v_{2},v_{3}\in V\setminus r$, let
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}$,
${v_{1}}^{\downarrow}\cap{v_{2}}^{\downarrow}=\emptyset$ and
${v_{1}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. If there exists a
min cut as in CASE-7 such that
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a min-cut then $v_{1}\in{\mathcal{S}}^{2}(v_{2},v_{3})$

###### Proof.

If such a min-cut exists then all the edges going out of the vertex set
${v_{2}}^{\downarrow}\setminus{v_{3}}^{\downarrow}$ apart from
$(\pi\left(v_{2}\right),v_{2})$ and $((\pi\left(v_{3}\right),v_{3}))$ goes to
the vertex set ${v_{1}}^{\downarrow}$. Thus the reduced canonical tree
$R({v_{2}}^{\downarrow}\setminus{v_{3}}^{\downarrow})$ contains node $v_{1}$.
We showcase this scenario in Fig. 5.20. Also the branching number of $v_{1}$
will be
$\mathcal{\xi}_{{R({v_{2}}^{\downarrow}\setminus{v_{3}}^{\downarrow})}}\left(v_{1}\right)=2$
based on the definition. Thus $v_{1}\in{\mathcal{S}}^{2}(v_{2},v_{3})$

Figure 5.8: Reduced sketch ${\mathcal{S}}^{2}(v_{2},v_{3})$ when for some
$v_{1},v_{2},v_{3}\in V\setminus r$, let
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}$,
${v_{1}}^{\downarrow}\cap{v_{2}}^{\downarrow}=\emptyset$ and
${v_{1}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$ and
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a min-cut

∎

######  Lemma 5.20.

For some $v_{1},v_{2},v_{3}\in V\setminus r$, let
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}$,
${v_{1}}^{\downarrow}\cap{v_{2}}^{\downarrow}=\emptyset$ and
${v_{1}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. If there exists a
min cut as in CASE-7 such that
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a min-cut then it can be found in $O(D^{2})$ time.

###### Proof.

Here we run Algorithm 9 on each node.

1 _Past Knowledge_

2 ${\mathcal{S}}^{2}(v,x)$ for all $v\in\mathcal{A}\left(x\right)$ using Lemma
5.16

3 For each $u\in\mathcal{A}\left(x\right)$, $x$ knows
$H_{{x}^{\downarrow}}^{u}$ and $\eta(u)$

1 for  _$v\in\mathcal{A}\left(x\right)\setminus x$_ do

2 for  _$u\in{\mathcal{S}}^{2}(v,x)\ \ &\ u\notin\mathcal{A}\left(x\right)$_
do

3 if
_$\eta(v)-1=H_{{x}^{\downarrow}}^{v}+\gamma({u}^{\downarrow},{v}^{\downarrow}\setminus{x}^{\downarrow})\
\ &$
$\eta(u)-1=\gamma({u}^{\downarrow},{v}^{\downarrow}\setminus{x}^{\downarrow})\
\&$ $\eta(x)-1=H_{{x}^{\downarrow}}^{v}$_ then

4
$\left\\{(\pi\left(x\right),x),(\pi\left(v\right),v),(\pi\left(u\right),u)\right\\}$
is a min-cut

5

6

Algorithm 9 Algorithm to find an induced cut fo size $3$ as given in CASE-7 to
be run on all node $x\in V\setminus r$

By Lemma 3.6 the reported min-cut is correct. Further when Algorithm 9 is run
on node $v_{3}$ it will be able to make decision about the required min-cut
because by Observation 5.19 if there exists such a min-cut then
$v_{1}\in{\mathcal{S}}^{2}(v_{2},v_{3})$.

Also, this just requires $O(D^{2})$ time because computing reduced sketch
${\mathcal{S}}^{2}(v,x)$ at any node $x$ for all
$v\in\mathcal{A}\left(x\right)$ just takes $O(D^{2})$ rounds as per Lemma
5.16. ∎

###  5.2 Layered Algorithm

In the last section, we gave a technique to find a min-cut of size 3 as in
CASE-3, CASE-6 and CASE-7 using a special graph-sketch. In this section, we
will give an algorithm to find the min-cut as given by CASE-5. A $k$-Sketch
cannot be used to find a min-cut as in CASE-5 because here it is challenging
for one of the nodes to know the $6$ quantities as required by Lemma 3.6 using
a $k$-sketch. To resolve this challenge, we give layered algorithm where we
solve for min-cut iteratively many times.

Recall a min-cut as given by CASE-5 is as follows: for some node
$v_{1},v_{2},v_{3}\in V\setminus r$,
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a min-cut such that ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. For the introduction
of layered algorithm, let us assume that such a min-cut exists. Further let
$v_{1},v_{2}$ and $v_{3}$ be these specific nodes. In Fig. 5.9, we show a
pictorial representation of such a min-cut.

Figure 5.9: Min-cut of size $3$ as given by CASE-5

Similar to the previous section, we will use the characterization Lemma 3.6
which requires six quantities to make a decision about the min-cut. These are
$\eta(v_{1}),\eta(v_{2}),\eta(v_{3}),\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{3}}^{\downarrow},{v_{2}}^{\downarrow})$
and $\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow})$.

In this subsection, we will show that node $x=\operatorname{LCA}(v_{2},v_{3})$
can find all these six quantities. The challenge here is the fact that some of
these quantities have to come from node $v_{2}$ and/or $v_{3}$. Since node $x$
is higher up in the tree $\mathcal{T}$ than $v_{2},v_{3}$ thus the information
from node $v_{2},v_{3}$ when it travels up the tree may face contention from
other nodes in ${x}^{\downarrow}$. From Recall (from chapter 2) that
convergecast is such a technique to send data to nodes which are higher up in
the tree from nodes at a lower level. For convergecast to be efficient here we
need to couple it with a contention resolution mechanism. The idea is as
follows:

  * •

We calculate min-cuts of size one and two in sub-graphs _pivoted_ at nodes at
different level in the tree $\mathcal{T}$ (details are deferred to Section
5.2.1)

  * •

After the above step, each node computes its _one-cut detail_ and _two-cut
detail_ (definitions are deferred to Section 5.2.2)

  * •

Based on the above computation, if a min-cut exists as given by
$\textbf{CASE}-5$, then node $v_{2},v_{3}$ can designate themselves as special
nodes using Lemma 5.24. Thus, the information from node $v_{2}$ and node
$v_{3}$ could reach $LCA(v_{2},v_{3})$ efficiently.

####  5.2.1 Definition of Layered Algorithm

For any node $v\in V\setminus r$, let ${E}_{{v}^{\downarrow}}$ be the set of
edges whose both endpoints are in the vertex set $v^{\downarrow}$. Let
subgraph pivoted at any vertex $v\neq r$ be
$G_{v}\triangleq(v^{\downarrow}\cup\pi\left(v\right),{E}_{{v}^{\downarrow}}\cup(\pi\left(v\right),v))$.
Note that this definition is different from the subgraph rooted at $v$ because
here we add the extra edge $(\pi\left(v\right),v)$ and vertex $\pi(v)$.

_Layered Algorithm_ is a special type of algorithm where we will solve for
induced-cut of size one and two in a layered fashion. As usual, we will work
with the fixed BFS tree $\mathcal{T}$. Here we will solve for induced-cut of
size $1$ and $2$ repeatedly for $Depth(\mathcal{T})=D$ times. In the first
iteration, our algorithm solves for these induced cuts in the whole graph $G$.
Then it solves for the min-cuts of size $1$ and $2$ in all the sub-graph
pivoted at nodes at level $1$; that is in all sub-graphs in the set
$\left\\{G_{v}\mid\ell\left(v\right)=1\right\\}$, subsequently in the sub-
graphs for all nodes pivoted at level $2$ and so on until level $D$. This is
the _Layered Algorithm for min-cut_. We will showcase the utility of this
algorithm later. In Observation 5.21, we will argue that the layered algorithm
for min-cut takes $O(D^{2})$ rounds.

######  Observation 5.21.

The layered algorithm for min-cut runs in $O(D^{2})$ rounds.

###### Proof.

From Theorem 4.10 and Lemma 4.14, we know that cuts of size 1,2 can be found
in $O(D)$ rounds. For all graphs
$\left\\{G_{v}\mid\ell\left(v\right)=i\right\\}$ pivoted at any level $1\leq
i\leq D$ the algorithm to compute min-cut of size $1,2$ can be run
independently because none of the sub-graphs in the set
$\left\\{G_{v}\mid\ell\left(v\right)=i\right\\}$ share an edge. Thus it takes
$O(D)$ round to run the min-cut algorithm in all such graphs. Now to run for
all graphs pivoted at nodes at all levels it takes $O(D^{2})$ rounds. ∎

We will now define the notation for the sequence of subgraphs. This is a short
hand notation to say that a property is satisfied for a set of pivoted sub-
graphs. Let $r\rightarrow w_{1}\rightarrow w_{2}\rightarrow\cdots\rightarrow
w_{t}$ be a path in the BFS tree. Then we know that
$G_{w_{1}},G_{w_{2}},\ldots,G_{w_{t}}$ are subgraphs of $G$ as defined
earlier. Let $i,j\in[1,t]$ and $i\leq j$, then let
$G_{\left({w_{i}},{w_{j}}\right)}$ be a set of subgraphs such that
$G_{\left({w_{i}},{w_{j}}\right)}\triangleq\left\\{G_{w_{h}}\mid i\leq h\leq
j\right\\}$. We say a property is true for $G_{\left({w_{i}},{w_{j}}\right)}$
if it is true for all the subgraphs in the set.

######  Observation 5.22.

For some nodes $x$ and $v$, let $x\in{v}^{\downarrow}$. If
$(\pi\left(x\right),x)$ is a min-cut for the sub-graph $G_{v}$ then
$(\pi\left(x\right),x)$ is a min-cut for all sub-graphs in
$G_{\left({x},{v}\right)}$. Similarly, let $a,b$ be two nodes. Let node $z$ be
the LCA of node $a,b$ in $tree$ and $v$ be some node such that
${v}\in\mathcal{A}\left(z\right)$. If
$\left\\{(\pi\left(a\right),a),(\pi\left(b\right),b)\right\\}$ is a min cut
for the sub-graph $G_{v}$ then it a min-cut for all the sub-graphs in
$G_{\left({z},{v}\right)}$.

####  5.2.2 Application of layered algorithm

We will now showcase the application of the above-mentioned layered algorithm
in finding a min-cut as given by CASE-5. First, we will give a simple process
in Algorithm 10 to be run on individual nodes after the run of the _Layered
Algorithm for min-cut_. For each node $a$, this collects two quantities 1-cut
detail $\mathcal{D}^{1}(a)$ and 2-cut detail $\mathcal{D}^{2}(a)$ which
relevant information. After this information is collected by each node $a$ it
will be sent upwards via a convergecast technique described later.

Further, we will characterize CASE-5 in Lemma 5.24. Recall that in CASE-5, for
some node $v_{1},v_{2},v_{3}\in V\setminus r$,
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a min-cut such that ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. This will help us
prove that one of the information from
$\left\\{\mathcal{D}^{2}\left(v_{2}\right),\mathcal{D}^{2}\left(v_{3}\right),\left\\{\mathcal{D}^{1}\left(v_{3}\right),\mathcal{D}^{1}\left(v_{2}\right)\right\\}\right\\}$
will be received by $\operatorname{LCA}(v_{2},v_{3})$ after the convergecast
algorithm. And this will be enough to make a decision about the min-cut based
on the characterization given in Lemma 3.6.

1 _computing 1-cut detail_

2 $v\leftarrow$ closest node to $r$ such that $(\pi\left(a\right),a)$ is a
min-cut in $G_{v}$

3 $\mathcal{D}^{1}(a)=\langle
node:a,parent:\pi\left(a\right),eta:\eta(a),pivotnode:v,numedges:H_{{a}^{\downarrow}}^{v},pivotnodelevel:\ell\left(v\right)\rangle$

1 _computing 2-cut detail_

2 $vSet\leftarrow\\{u\mid\exists\text{ node }x\ s.t.\
{x}^{\downarrow}\cap{a}^{\downarrow}=\emptyset;\
\gamma({x}^{\downarrow},{a}^{\downarrow})>0;\
\ell\left(a\right)\geq\ell\left(x\right);\left\\{(\pi\left(a\right),a),(\pi\left(x\right),x)\right\\}$
$\text{ is a induced cut in }G_{u}\\}$

3 if  _ $vSet=\emptyset$ _ then $\mathcal{D}^{2}(a)=\phi$

4 else

5 $v\leftarrow\underset{u\in vSet}{argmin}\ \ell\left(u\right)$

6

7 $bSet\leftarrow\\{x\mid{x}^{\downarrow}\cap{a}^{\downarrow}=\emptyset;\
\gamma({x}^{\downarrow},{a}^{\downarrow})>0;\
\ell\left(a\right)\geq\ell\left(x\right);\left\\{(\pi\left(a\right),a),(\pi\left(x\right),x)\right\\}$
$\text{ is a induced cut in }G_{v}\\}$

8 $b\leftarrow\underset{x\in bSet}{argmin}\ \ell\left(x\right)$

9 $z\leftarrow\operatorname{LCA}\left(a,b\right)$

10 $\mathcal{D}^{2}(a)\triangleq\langle
node1:a,parent1:\pi\left(a\right),eta1:\eta(a),node1PivotOutEdges:H^{v}_{{a}^{\downarrow}},node2:b,parent2:\pi\left(b\right),eta2:\eta(b),node2PivotOutEdges:H^{v}_{{b}^{\downarrow}},betweenedges:\gamma({a}^{\downarrow},{b}^{\downarrow}),lca:z,lcalevel:\ell\left(z\right),pivotnode:v,pivotenodelevel:\ell\left(v\right)\rangle$

11

Algorithm 10 1-cut details and 2-cut details (to be run after layered
algorithm for min-cut on all nodes $a$)

######  Observation 5.23.

For each node $x$, $\mathcal{D}^{1}(x)$ (1-cut detail) and
$\mathcal{D}^{2}(x)$ (2-cut detail) can be computed in $O(D^{2})$ time as
given in Algorithm 10

###### Proof.

In Observation 5.21, we saw that the layered algorithm for min-cut runs in
$O(D^{2})$ time. We claim that after the layered algorithm for min-cut is
executed we have all the information to compute both 1-cut detail and 2-cut
detail. For 1-cut detail of a node $a$ we require $\eta(a)$ which node $a$
knows from the first section. Further, we require node $v$ closest to the root
such that the edge $(\pi\left(a\right),a)$ persists as a min-cut in the sub-
graph $G_{v}$. This node can be found after layered algorithm for min-cut is
run. Also $H_{{a}^{\downarrow}}^{v}$ is available with node $a$ from Section
4.1.

Similarly for 2-cut detail. Here the layered algorithm uses Lemma 4.23, which
takes $O(D)$ rounds. At the end of the layered algorithm for the min-cut every
node $a$ knows all the required induced-cut of size $2$ that it participates
in subgraph $G_{v}$ for all $v\in\mathcal{A}\left(a\right)$. Based on that, it
can calculate 2-cut detail. ∎

Now, we will give characterization of $\textbf{CASE}-5$. This characterization
will help us to desginate node $v_{2},v_{3}$ as special nodes in
${x}^{\downarrow}$.

######  Lemma 5.24.

Let the graph $G$ be 3-connected (there are no min-cuts of size $1$ and $2$ in
$G$). Let $v_{1},v_{2},v_{3}\in V\setminus\left\\{r\right\\}$,
${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$, let
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
be a min-cut (as in CASE-5). Then the following statements are true

  1. i)

Let
$x\in{v_{1}}^{\downarrow}\setminus\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$
and $x$ is not on either of the path $\rho(v_{2}),\rho(v_{3})$ then the edge
$(\pi\left(x\right),x)$ is not a min-cut in $G_{v_{1}}$

  2. ii)

when $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$,
$(\pi\left(v_{2}\right),v_{2})$ and $(\pi\left(v_{3}\right),v_{3})$ are 1-cuts
for sub-graph in $G_{\left({v_{2}},{v_{1}}\right)}$ and
$G_{\left({v_{3}},{v_{1}}\right)}$ respectively

  3. iii)

Let
$x\in{v_{1}}^{\downarrow}\setminus\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$
be a node and let $x$ not be on either of the two paths
$\rho(v_{2}),\rho(v_{3})$ and also let
$\ell\left(x\right)\in\left\\{\ell\left(v_{2}\right),\ell\left(v_{3}\right)\right\\}$.
When $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$, then there does
not exists a node $y$ such that
${x}^{\downarrow}\cap{y}^{\downarrow}=\emptyset$,
$\gamma({x}^{\downarrow},{y}^{\downarrow})>0$ and the edge set
$\left\\{(\pi\left(x\right),x),(\pi\left(y\right),y)\right\\}$ is a induced
cut of size $2$ in $G_{v_{1}}$

  4. iv)

Let node $z$ be the LCA of $v_{2},v_{3}$. When
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$ then
$\left\\{(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a 2-cut for sub-graph sequence $G_{\left({z},{v_{1}}\right)}$

  5. v)

When $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$ then there does not
exists a node $x$ on the path $\rho(v_{2})$ such that
$\ell\left(x\right)<\ell\left(v_{2}\right)$,
${x}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$ and
$\left\\{(\pi\left(x\right),x),(\pi\left(v_{3}\right),v_{3})\right\\}$ is an
induced cut of $G_{v_{1}}$

######  Observation 5.25.

If there is an induced cut as given in Lemma 5.24, then no node in the set
${v_{1}}^{\downarrow}\setminus\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$
is connected to any node in $V\setminus{v_{1}}^{\downarrow}$. Also apart from
the edges $(\pi\left(v_{2}\right),v_{2})$ and $(\pi\left(v_{3}\right),v_{3})$
node in $\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$ do not
have any edge with nodes in
${v_{1}}^{\downarrow}\setminus\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$.

###### Proof.

If such was the case then
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
would not have been a min-cut. We will prove the above claims using this
simple observation. ∎

###### Proof of Lemma 5.24.

  1. i)

As per given condition $v_{2}\notin{x}^{\downarrow}$ and
$v_{3}\notin{x}^{\downarrow}$. By Observation 5.25, the only nodes in
${v_{1}}^{\downarrow}$ which have an adjacent edge to the nodes in
$V\setminus{v_{1}}^{\downarrow}$ are in the vertex sets ${v_{2}}^{\downarrow}$
or ${v_{3}}^{\downarrow}$. Now since $(\pi\left(x\right),x)$ is a min-cut in
$G_{v_{1}}$ thus no node in ${x}^{\downarrow}$ has an adjacent edge with a
node in $V\setminus{v_{1}}^{\downarrow}$ . Thus if $(\pi\left(x\right),x)$ is
a min-cut for the sub-graph $G_{v_{1}}$ then it is also a min-cut edge in the
whole graph $G$ which is a contradiction because the graph is 3-connected.

  2. ii)

Since $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$ thus there are no
edges between vertices in the sets ${v_{2}}^{\downarrow}$ and
${v_{3}}^{\downarrow}$. Also there are no edges between vertices in the vertex
set ${v_{1}}^{\downarrow}\setminus{v_{2}}^{\downarrow}$ and
${v_{2}}^{\downarrow}$. Thus $(\pi\left(v_{2}\right),v_{2})$ is a cut-edge in
subgraph $G_{v_{1}}$ and in all the subgraphs in
$G_{\left({v_{2}},{v_{1}}\right)}$ by Observation 5.22. Similarly for the edge
$(\pi\left(v_{3}\right),v_{3})$.

  3. iii)

Lets consider the simple case when $y$ is in either ${v_{2}}^{\downarrow}$ or
${v_{3}}^{\downarrow}$. Here
$\gamma\left({x}^{\downarrow},{y}^{\downarrow}\right)=0$ by Observation 5.25

The other case when $(\pi\left(y\right),y)$ is on one of the paths out of
$\rho(v_{2})$ or $\rho(v_{3})$. WLOG let $(\pi\left(y\right),y)$ be on the
path $\rho(v_{2})$. Thus ${v_{2}}^{\downarrow}\subseteq{y}^{\downarrow}$. Also
given that $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$ thus
$\left\\{(\pi\left(x\right),x),(\pi\left(y\right),y)\right\\}$ cannot be a cut
induced by $\delta({x}^{\downarrow}\oplus{y}^{\downarrow})$ in $G_{v_{1}}$
since ${v_{2}}^{\downarrow}\subseteq{y}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subseteq{v_{1}}^{\downarrow}\setminus({x}^{\downarrow}\cup{y}^{\downarrow})$
thus the vertex set ${x}^{\downarrow}\cup{y}^{\downarrow}$ and
${v_{1}}^{\downarrow}\setminus({x}^{\downarrow}\cup{y}^{\downarrow})$ have at
least one edge between them

Now let $y$ be not on either of the path $\rho(v_{2})$ or $\rho(v_{3})$. Also
$y$ is not in either of the vertex set ${v_{2}}^{\downarrow}$ and
${v_{3}}^{\downarrow}$. Now, as per given condition, $(\pi\left(x\right),x)$
is not on either of the path $\rho(v_{2})$ or $\rho(v_{3})$. Since both the
edges are not on the paths $\rho(v_{2})$ and $\rho(v_{3})$ thus neither of
$v_{2}$ or $v_{3}$ are in the vertex set ${x}^{\downarrow}$ or
${y}^{\downarrow}$. If here
$\left\\{(\pi\left(x\right),x),(\pi\left(y\right),y)\right\\}$ is a min-cut
then there are edges between vertices of the two sets ${x}^{\downarrow}$ and
${y}^{\downarrow}$ and they do not have any other edge to the vertices in
${v_{1}}^{\downarrow}\setminus({x}^{\downarrow}\cup{y}^{\downarrow})$. Also
here by Observation 5.25 nodes in ${x}^{\downarrow}\cup{y}^{\downarrow}$ do
not have any edge in $V\setminus{v_{1}}^{\downarrow}$. Thus by the above two
statements nodes in ${x}^{\downarrow}\cup{y}^{\downarrow}$ do not have any
adjacent edges to nodes in $V\setminus({x}^{\downarrow}\cup{y}^{\downarrow})$
hence, the edge set
$\left\\{(\pi\left(x\right),x),(\pi\left(y\right),y)\right\\}$ persists as a
min-cut in the whole graph which is a contradiction because the graph is
3-connected.

  4. iv)

Since $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$ thus there are
some edges between vertices of the sets ${v_{2}}^{\downarrow}$ and
${v_{3}}^{\downarrow}$. Also by Observation 5.25 there are no edges between
vertices in the vertex set
${v_{1}}^{\downarrow}\setminus({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})$
and ${v_{2}}^{\downarrow}$. Similarly there are no edges between vertices in
the vertex set
${v_{1}}^{\downarrow}\setminus({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})$
and ${v_{3}}^{\downarrow}$. Here $z$ is the LCA of $v_{2},v_{3}$ and there are
edges which go between ${v_{2}}^{\downarrow}$ and ${v_{3}}^{\downarrow}$.
Also, by Observation 5.25 no edges other than
$\left\\{(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
connect nodes in
${z}^{\downarrow}/({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})$ to nodes in
${v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}$. Thus
$\left\\{(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
is a 2-cut in $G_{z}$. Similar argument can be given for all sub-graphs in the
graph sequence $G_{\left({z},{v_{1}}\right)}$

  5. v)

As per the given condition
$x\in{v_{1}}^{\downarrow}\setminus({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})$
and $v_{2}\in{x}^{\downarrow}$. We will focus on the vertex set
${x}^{\downarrow}\setminus{v_{2}}^{\downarrow}$ which is not empty because
$\ell\left(x\right)<\ell\left(v_{2}\right)$. If
$\left\\{(\pi\left(x\right),x),(\pi\left(v_{3}\right),v_{3})\right\\}$ is an
induced cut of $G_{v_{1}}$ then vertices in the set
${x}^{\downarrow}\cup{v_{3}}^{\downarrow}$ do not have an adjacent edge to
vertices in
${v_{1}}^{\downarrow}\setminus({x}^{\downarrow}\cup{v_{3}}^{\downarrow})$.
Thus vertices in ${x}^{\downarrow}\setminus{v_{2}}^{\downarrow}$ does not have
an adjacent edge to vertices in
${v_{1}}^{\downarrow}\setminus({x}^{\downarrow}\cup{v_{3}}^{\downarrow})$.
Further
${x}^{\downarrow}\setminus{v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}\setminus({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})$
thus by Observation 5.25 vertices in
${x}^{\downarrow}\setminus{v_{2}}^{\downarrow}$ do not have an adjacent edge
to vertices in $V\setminus{v_{1}}^{\downarrow}$. Hence
$\delta({x}^{\downarrow}\setminus{v_{2}}^{\downarrow})=\left\\{(\pi\left(x\right),{x}),(\pi\left(v_{2}\right),{v_{2}})\right\\}$
is an induced cut in the whole graph which is a contradiction.

∎

Now we will give a variant of a convergecast algorithm for communicating 1-cut
details and 2-cut detail of a node to the ancestors in Algorithm 11. Similarly
for 2-cut detail. Note that for any node $v$ it will not receive all
$\mathcal{D}^{1}(x)$ and $\mathcal{D}^{2}(x)$ for all $x\in{v}^{\downarrow}$
but the ones which are relevant among others. We will characterize this in
Observation 5.26.

1 _convergecasting 1-cut detail_

2 if  _node $a$ is a leaf node_ then

3 send $<\mathcal{D}^{1}(a),\ell\left(a\right)>$ to $\pi\left(a\right)$

4 else if  _node $a$ is a internal node_ then

5 for  _round $t=0$_ do send $<\mathcal{D}^{1}(a),\ell\left(a\right)>$ to
$\pi\left(a\right)$

6 for  _each subsequet round $t=1$ to $t=D-\ell\left(a\right)$_ do

7 collect message $\operatorname{msg}_{c}$ from all node
$c\in\operatorname{children}(a)$

8 if  _$\operatorname{msg}_{c}=\phi\ \forall c\in\operatorname{children}(a)$_
then send $<\phi,\ell\left(a\right)+t>$ to $\pi\left(a\right)$

9 else

10 $\mathcal{D}\leftarrow$ among $\operatorname{msg}_{c}\forall
c\in\operatorname{children}(a)$ choose the 1-cut detail from which 1-cut
persists for the sub-graph closest to the root that is the lowest $6^{th}$
element (last) of the 1-cut detail tuple

11 send $<\mathcal{D},\ell\left(a\right)+t>$ to $\pi\left(a\right)$

12

13

14

1

2 _convergecasting 2-cut detail_

3 if  _node $a$ is a leaf node_ then

4 send $<\mathcal{D}^{2}(a),\ell\left(a\right)>$ to $\pi\left(a\right)$

5 else if  _node $a$ is a internal node_ then

6 for  _round $t=0$_ do send $<\mathcal{D}^{2}(a),\ell\left(a\right)>$ to
$\pi\left(a\right)$

7 for  _each subsequet round $t=1$ to $t=D-\ell\left(a\right)$_ do

8 collect message $\operatorname{msg}_{c}$ from all node
$c\in\operatorname{children}(a)$

9 if  _$\operatorname{msg}_{c}=\phi\ \forall c\in\operatorname{children}(a)$_
then send $<\phi,\ell\left(a\right)+t>$ to $\pi\left(a\right)$

10 else

11 $\mathcal{D}\leftarrow$ among $\operatorname{msg}_{c}\forall
c\in\operatorname{children}(a)$ choose the 2-cut detail for which 2-cut
persists for the sub-graph closest to the root that is the lowest $11^{th}$
element (last) of the 2-cut detail tuple

12 send $<\mathcal{D},\ell\left(a\right)+t>$ to $\pi\left(a\right)$

13

14

15

Algorithm 11 Converge-cast algorithm to be run at every node $a$

######  Observation 5.26.

For some nodes $v_{1},v_{2},v_{3}\in V\setminus\left\\{r\right\\}$, let
${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. Let
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
be a min-cut (as in CASE-5). If
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$ then at the end of the
Algorithm 11, $\operatorname{LCA}(v_{2},v_{3})$ has both
${\mathcal{D}^{1}(v_{2})},\mathcal{D}^{1}(v_{3})$. And when
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$ then it has either of
$\mathcal{D}^{2}(v_{2})$, $\left\\{\mathcal{D}^{2}(v_{3})\right\\}$. Also
Algorithm 11 takes $O(D)$ rounds.

###### Proof.

Let $z$ be the LCA of node $v_{2},v_{3}$. Lets first consider
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$. Here based on Lemma
5.24 (i and ii) we can say that there does not exists a node
$x\in{v_{1}}^{\downarrow}\setminus\left({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}\right)$
such that $(\pi\left(x\right),x)$ persists as a min-cut in $G_{v_{1}}$. Thus
at line 11 of Algorithm 11, $\mathcal{D}^{1}(v_{2})$ will not have a
contention at any node $u\in\mathcal{A}\left(v_{2}\right)$ such that
$\ell\left(u\right)>\ell\left(z\right)$. Similarly for $v_{3}$. The first
contention happen at node $z$ (LCA of $v_{2}$ and $v_{3}$). Let $z$ be the LCA
of node $v_{2},v_{3}$. Here $z$ will have both $\mathcal{D}^{1}(v_{2})$ and
$\mathcal{D}^{1}(v_{3})$ received from two different children
$c_{1},c_{2}\in\operatorname{children}(z)$.

Now when $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$. Here by Lemma
5.24 (pt. iv) we know that
$\left\\{(\pi\left(v_{2}\right),{v_{2}}),(\pi\left(v_{3}\right),{v_{3}})\right\\}$
is an induced 2-cut. WLOG Lets assume
$\ell\left(v_{2}\right)\leq\ell\left(v_{3}\right)$. Thus using Algorithm 7
node $v_{2}$ can make a decision about the said induced cut of size 2. Also
$\mathcal{D}^{2}(v_{2})$ (2-cut detail of node $v_{2}$) contains information
about the induced cut
$\left\\{(\pi\left(v_{2}\right),{v_{2}}),(\pi\left(v_{3}\right),{v_{3}})\right\\}$
because there does not exists any other node $x$ as per Lemma 5.24 (pt. v)
such that $\ell\left(x\right)<\ell\left(v_{3}\right)$ and
$\left\\{(\pi\left(x\right),{x}),(\pi\left(v_{2}\right),{v_{2}})\right\\}$ is
an induced cut of size 2 in $G_{v_{1}}$. Further using the Lemma 5.24 (pt. ii)
there will not be any contention for $\mathcal{D}^{2}(v_{2})$ to reach to
$\operatorname{LCA}(v_{2},v_{3})$.

Also both the converge-casting modules in Algorithm 11 run for $O(D)$ time
because both 1-cut detail and 2-cut detail are of the size $O(\log n)$ bits
and for each node the modules run for atmost $O(D)$ rounds. ∎

######  Lemma 5.27.

For some nodes $v_{1},v_{2},v_{3}\in V\setminus\left\\{r\right\\}$, let
${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$ . Let
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),(\pi\left(v_{3}\right),v_{3})\right\\}$
be a min-cut (as in CASE-5). Then we can find this min-cut in $O(D^{2})$
rounds.

###### Proof.

Here we run Algorithm 12 on each node $x$. This algorithm is run after the
convergecast of 1-cut details and 2-cut details. This algorithm has two parts:
finding min-cut from 1-cut detail and from 2-cut detail as given in Algorithm
11. We will argue that all the min-cuts of the form as given by CASE-5 are
correctly found by this algorithm. And also prove that this process takes
$O(D^{2})$ rounds.

We claim that when Algorithm 12 is run on LCA of $v_{2},v_{3}$ then it can
find the required min-cut. Firstly, let see the case where
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$ here as per Observation
5.26 the LCA of $v_{2},v_{3}$ has both $\mathcal{D}^{1}(v_{2})$ and
$\mathcal{D}^{1}(v_{3})$. Let $v$ be the pivotnode from
$\mathcal{D}^{1}(v_{2})$ and $u$ be the pivotnode from
$\mathcal{D}^{1}(v_{3})$. The information regarding
$H_{{v_{2}}^{\downarrow}}^{v}$ and $H_{{v_{3}}^{\downarrow}}^{u}$ is available
from the respective one cut detail. WLOG let
$\ell\left(v\right)\geq\ell\left(u\right)$. Thus here
$H_{{v_{3}}^{\downarrow}}^{u}=H_{{v_{3}}^{\downarrow}}^{v}$ because the number
of edges going out of the vertex set ${v_{3}}^{\downarrow}$ which also goes
out of the vertex ${u}^{\downarrow}$ is same as the number of edges going out
of the vertex set ${v_{3}}^{\downarrow}$ which also goes out of the vertex
${v}^{\downarrow}$. Now if the condition in Line 12 is satisfied then the min-
cut is correctly found as per Lemma 3.6.

Further, moving to case when
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})>0$. Here as per Observation
5.26 one of $\mathcal{D}^{2}(v_{2})$ or $\mathcal{D}^{2}(v_{3})$ is present at
node $v_{3}$. And when condition at Line 12 then the min-cut is correctly
found as per Lemma 3.6.

1 _from 1-cut detail_

2
$nodePair\leftarrow\left\\{(a,b)\mid\mathcal{D}^{1}(a),\mathcal{D}^{1}(b)\text{
where received from two nodes
}c_{1},c_{2}\in\operatorname{children}(v)\right\\}$

3 for  _each $(a,b)\in nodePair$_ do

4 $v\leftarrow pivotnode$ from $\mathcal{D}^{1}(a),u\leftarrow pivotnode$ from
$\mathcal{D}^{1}(b)$

5 $z\leftarrow\underset{z^{\prime}\in\left\\{v,u\right\\}}{argmax\
}\ell\left(z^{\prime}\right)$

6 if  _$\eta(z)-1=H_{{a}^{\downarrow}}^{z}+H_{{b}^{\downarrow}}^{z}$ &
$\eta(a)-1=H_{{a}^{\downarrow}}^{z}$ & $\eta(b)-1=H_{{b}^{\downarrow}}^{z}$_
then

7
$\left\\{(\pi\left(z\right),{z}),(\pi\left(a\right),{a}),(\pi\left(b\right),{b})\right\\}$
is a min-cut

8

9

1

2 _from 2-cut detail_

3 for  _all node $a$ such that $\mathcal{D}^{2}(a)$ was received_ do

4 $a,b$ be $node1$ and $node2$ in $\mathcal{D}^{2}(a)$; $v$ be the pivotNode
from $\mathcal{D}^{2}(a)$

5 if  _$\eta(v)-1=H_{{a}^{\downarrow}}^{v}+H_{{b}^{\downarrow}}^{v}$ &
$\eta(a)-1=H_{{a}^{\downarrow}}^{v}+\gamma({a}^{\downarrow},{b}^{\downarrow})$&
$\eta(b)-1=H_{{b}^{\downarrow}}^{v}+\gamma({a}^{\downarrow},{b}^{\downarrow})$_
then

6
$\left\\{(\pi\left(v\right),{v}),(\pi\left(a\right),{a}),(\pi\left(b\right),{b})\right\\}$
is a min-cut

7

8

Algorithm 12 Algorithm to find min-cut as given by CASE-5 (to be run at each
internal node $x$)

Also, this whole process just takes $O(D^{2})$ rounds because the layered
algorithm for min-cut takes $O(D^{2})$ rounds and the covergecast algorithm
given in Algorithm 11 takes just $O(D)$ rounds. ∎

###  5.3 Summary

In this chapter, we gave noval deterministic algorithm to find min-cuts of
size $3$. The backbone of our algorithm is the characterization presented in
Lemma 3.5 and Lemma 3.6. In this chapter, we showed that whenever there exists
a min-cut of size $3$ at least one node in the whole network will receive the
required quantities as per the characterization in $O(D^{2})$ rounds and thus
the min-cut will be found.

The communication strategies introduced in this chapter are of two flavours:
_Sketching_ technique where we collected small but relevant information and
_Layered Algorithm_ which is a convergecast technique based on a contention
resolution mechanism.

##  Chapter 6 Future Work

We have discussed techniques for finding min-cut. Before our result, a decade
old work existed to find small min-cuts by [25]. They gave an algebraic
technique of random circulation for finding min-cut of size $1$ and $2$. On
the contrary, we give deterministic and purely combinatorial techniques for
finding min-cuts of size $1,2$ and $3$. Our algorithm takes $O(D)$ rounds for
finding min-cut of size $1,2$ and $O(D^{2})$ rounds for finding min-cut of
size $3$. An immediate future goal could be to prove that the lower bound
$O(D^{2})$ for a min-cut of size $3$ which is not trivial.

Currently, there are some fundamental issues for finding min-cuts of size $4$
and above using our techniques. It would be interesting to extend our
techniques for min-cut of size $4$. We are hopeful about it and give the
following conjecture

######  Conjecture 1.

There exists a distributed algorithm to find if a min-cut of size $k=o(\log
n)$ exists in $\tilde{O}(D^{k})$ rounds.

## References

  * Ahuja and Zhu [1989] Ahuja, M. and Y. Zhu, An efficient distributed algorithm for finding articulation points, bridges, and biconnected components in asynchronous networks.  In Foundations of Software Technology and Theoretical Computer Science, FSTTCS. 1989.
  * [2] Bondy, J. A. and U. S. R. Murty, Graph theory with applications, volume 290.  Citeseer, .
  * Das Sarma et al. [2011] Das Sarma, A., S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer, Distributed verification and hardness of distributed approximation.  In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC. 2011.
  * Elkin [2017] Elkin, M., A simple deterministic distributed mst algorithm, with near-optimal time and message complexities.  In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC. 2017.
  * Elkin and Neiman [2017] Elkin, M. and O. Neiman (2017).  Linear-size hopsets with small hopbound, and distributed routing with low memory.  URL http://arxiv.org/abs/1704.08468.
  * Gabow [1991] Gabow, H. N., A matroid approach to finding edge connectivity and packing arborescences.  In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC ’91. ACM, New York, NY, USA, 1991.  ISBN 0-89791-397-3.  URL http://doi.acm.org/10.1145/103418.103436.
  * Ghaffari and Haeupler [2016] Ghaffari, M. and B. Haeupler, Distributed algorithms for planar networks - ii: Low-congestion shortcuts, mst, and min-cut.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2016.
  * Ghaffari and Kuhn [2013] Ghaffari, M. and F. Kuhn, Distributed minimum cut approximation.  In International Symposium on Distributed Computing. Springer, 2013.
  * Henzinger et al. [2017] Henzinger, M., S. Rao, and D. Wang, Local flow partitioning for faster edge connectivity.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2017.
  * Hohberg [1990] Hohberg, W. (1990).  How to find biconnected components in distributed networks.  J. Parallel Distrib. Comput., 9(4), 374–386.  ISSN 0743-7315.  URL http://dx.doi.org/10.1016/0743-7315(90)90122-6.
  * Karger [1993] Karger, D. R., Global min-cuts in rnc, and other ramifications of a simple min-out algorithm.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1993.  ISBN 0-89871-313-7.  URL http://dl.acm.org/citation.cfm?id=313559.313605.
  * Karger [1994a] Karger, D. R., Random sampling in cut, flow, and network design problems.  In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC ’94. ACM, New York, NY, USA, 1994a.  ISBN 0-89791-663-8.  URL http://doi.acm.org/10.1145/195058.195422.
  * Karger [1994b] Karger, D. R., Using randomized sparsification to approximate minimum cuts.  In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’94. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1994b.  ISBN 0-89871-329-3.  URL http://dl.acm.org/citation.cfm?id=314464.314582.
  * Karger [2000] Karger, D. R. (2000).  Minimum cuts in near-linear time.  J. ACM, 47(1), 46–76.  ISSN 0004-5411.  URL http://doi.acm.org/10.1145/331605.331608.
  * Karger and Stein [1993] Karger, D. R. and C. Stein, An õ (n 2) algorithm for minimum cuts.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993.
  * Kawarabayashi and Thorup [2015] Kawarabayashi, K.-i. and M. Thorup, Deterministic global minimum cut of a simple graph in near-linear time.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, STOC. 2015.
  * Kutten and Peleg [1998] Kutten, S. and D. Peleg (1998).  Fast distributed construction of smallk-dominating sets and applications.  J. Algorithms, 28(1).
  * Luby [1985] Luby, M., A simple parallel algorithm for the maximal independent set problem.  In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC. 1985.
  * Matula [1993] Matula, D. W., A linear time 2 + &&egr;&egr; approximation algorithm for edge connectivity.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1993.  ISBN 0-89871-313-7.  URL http://dl.acm.org/citation.cfm?id=313559.313872.
  * Nagamochi and Ibaraki [1992] Nagamochi, H. and T. Ibaraki (1992).  Computing edge-connectivity in multigraphs and capacitated graphs.  SIAM Journal on Discrete Mathematics, 5(1), 54–66.
  * Nanongkai and Su [2014] Nanongkai, D. and H.-H. Su, Almost-tight distributed minimum cut algorithms.  In 24th International Symposium on Distributed Computing, DISC. 2014.
  * Pandurangan et al. [2017] Pandurangan, G., P. Robinson, and M. Scquizzato, A time- and message-optimal distributed algorithm for minimum spanning trees.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC. 2017.
  * Peleg [2000] Peleg, D., Distributed computing: a locality-sensitive approach.  SIAM, 2000.
  * Pritchard [2006] Pritchard, D. (2006).  An optimal distributed edge-biconnectivity algorithm.  Accepted as a Poster at 25th ACM symposium on Principles of distributed computing. PODC..  URL http://arxiv.org/abs/cs/0602013.
  * Pritchard [2008] Pritchard, D., Fast distributed computation of cuts via random circulations.  In International Colloquium on Automata, Languages, and Programming, ICALP. 2008.
  * Pritchard and Thurimella [2011] Pritchard, D. and R. Thurimella (2011).  Fast computation of small cuts via cycle space sampling.  ACM Transactions on Algorithms (TALG), 7(4), 46.
  * Stoer and Wagner [1997] Stoer, M. and F. Wagner (1997).  A simple min-cut algorithm.  J. ACM, 44(4), 585–591.  ISSN 0004-5411.  URL http://doi.acm.org/10.1145/263867.263872.
  * Thorup [2001] Thorup, M., Fully-dynamic min-cut.  In Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, 2001.
  * Thurimella [1995] Thurimella, R., Sub-linear distributed algorithms for sparse certificates and biconnected components.  In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, PODC. 1995.
  * Tsin [2006] Tsin, Y. H. (2006).  An efficient distributed algorithm for 3-edge-connectivity.  International Journal of Foundations of Computer Science, 17(03), 677–701.

## CURRICULUM VITAE

1. | NAME | : | Mohit Daga
---|---|---|---
2. | DATE OF BIRTH | : | July 5, 1993
3. | EDUCATION QUALIFICATIONS |  |

  1. (a)

Bachelor of Technology

Institute | : | The LNM Institute of Information Technology, Jaipur
---|---|---
Specialization | : | Communication and Computer Engineering

  2. (b)

M.S. By Research

Institute | : | Indian Institute of Technology - Madras
---|---|---
Registration Date | : | January 6, 2016

## GENERAL TEST COMMITTEE

CHAIRPERSON | : | Prof. N.S. Narayanaswamy
---|---|---
|  | Professor
|  | Department of Computer Science and Engineering
GUIDE | : | Dr. John Augustine
|  | Associate Professor
|  | Department of Computer Science and Engineering
MEMBERS | : | Dr. Shweta Agrawal
|  | Assistant Professor
|  | Department of Computer Science and Engineering
|  | Dr. Krishna Jagannathan
|  | Assistant Professor
|  | Department of Electrical Engineering