Improved Algorithm for Min-Cuts in Distributed Networks

COMPUTER SCIENCE AND ENGINEERING

# Improved Algorithm for Min-Cuts in Distributed Networks

Mohit Daga

(OCTOBER 2017)

###### Abstract

KEYWORDS:  Connectivity, Reliability, Edge Min-Cuts

In this thesis, we present fast deterministic algorithm to find small cuts in
distributed networks. Finding small min-cuts for a network is essential for
ensuring the quality of service and reliability. Throughout this thesis, we
use the CONGEST model which is a typical message passing model used to design
and analyze algorithms in distributed networks. We survey various algorithmic
techniques in the CONGEST model and give an overview of the recent results to
find cuts. We also describe elegant graph theoretic ideas like cut spaces and
cycle spaces that provide useful intuition upon which our work is built.

Our contribution is a novel fast algorithm to find small cuts. Our algorithm
relies on a new characterization of trees and cuts introduced in this thesis.
Our algorithm is built upon several new algorithmic ideas that, when coupled
with our characterization of trees and cuts, help us to find the required min-
cuts. Our novel techniques include a _tree restricted semigroup function
(TRSF)_ , a novel _sketching_ technique, and a _layered algorithm_. TRSF is
defined with respect to a spanning tree and is based on a commutative
semigroup. This simple yet powerful technique helps us to deterministically
find min-cuts of size one (bridges) and min-cuts of size two optimally. Our
sketching technique samples a small but relevant vertex set which is enough to
find small min-cuts in certain cases. Our layered algorithm finds min-cuts in
smaller sub-graphs _pivoted_ by nodes at different levels in a spanning tree
and uses them to make the decision about the min-cuts in the complete graph.
This is interesting because it enables us to show that even for a global
property like finding min-cuts, local information can be exploited in a
coordinated manner.

This is to certify that the thesis titled Improved Algorithm for Min-Cuts in
Distributed Networks, submitted by Mohit Daga, to the Indian Institute of
Technology, Madras, for the award of the degree of Master of Science, is a
bona fide record of the research work done by him under my supervision. The
contents of this thesis, in full or in parts, have not been submitted to any
other Institute or University for the award of any degree or diploma.

Dr. John Augustine
Research Guide
Associate Professor
Dept. of CSE
IIT-Madras, 600 036

Place: Chennai
Date:

###### Acknowledgements.

First and foremost, I would like to extend my sincere gratitude to my thesis
supervisor Dr. John Augustine. I am thankful to John for his constant
encouragement, guidance and optimism. John actively helped me in improving my
technical writing and presentation with lot of patience. Our countless
discussions about research (we literally burnt the midnight oil) enabled the
timely completion of this thesis. His opinion and vision about a career in
research and academia are well placed. I also closely collaborated with Dr.
Danupon Nanongkai, who introduced me to the problem covered in this thesis. I
thank him for inviting me to KTH in April’17. Danupon also reviewed a draft of
this work and gave me valuable inputs. During the initial days at IIT-Madras,
I interacted with Dr. Rajseakar Manokaran, in his capacity as my faculty
adviser. He inspired me to pursue research in Theoretical Computer Science. I
thank Dr. N.S. Narayanaswamy, chairperson of my General Test Committee (GTC)
for being critical of my seminar presentations and helping me to grow as a
researcher. I also thank Dr. Krishna Jagannathan and Dr. Shweta Agrawal for
accepting to be part of my GTC. I feel proud to be part of IIT Madras and CSE
Department. I thank the administration here for establishing tranquility and
serenity of campus after the devastating 2016 cyclone. I thank the support
staff of my department. Special thanks to Mr. Mani from the CSE office for
scheduling the required meetings and helping me to understand the procedures
and requirements with patience. During my stay at IIT Madras, I was part of
two groups: ACT Lab and TCS Lab. I thank my lab mates for maintaining good
work culture. My various discussions on a wide range of topics with my lab
mates were enjoyable and enriching. This experience will be helpful when I
move to Stockholm for my Ph.D. studies. Last but not the least, I thank my
mother Beena, my father Manohar and my sisters: Kaushal and Sheetal. This
thesis is dedicated to them.

###### Contents

  1. NOTATION
  2. 1 Introduction
    1. 1.1 Notations and Conventions
    2. 1.2 Distributed Model
    3. 1.3 Classification of network problems based on locality
    4. 1.4 Overview of past results
    5. 1.5 Organization of this thesis
  3. 2 Preliminaries and Background
    1. 2.1 Simple algorithms in Distributed Networks
      1. 2.1.1 Tree Constructions and Notations
      2. 2.1.2 Convergecast and Broadcast
    2. 2.2 Cuts Space and Cycle Space
    3. 2.3 Min-Cuts in Distributed Networks
      1. 2.3.1 Using Greedy Tree Packing
      2. 2.3.2 Using Random Circulations
  4. 3 Technical Overview
    1. 3.1 Characterization of Trees and Cuts
    2. 3.2 Our Contribution
  5. 4 Tree Restricted Semigroup Function
    1. 4.1 Min-Cuts of size 1
    2. 4.2 Min-Cuts of size 2
  6. 5 Min-Cuts of size three
    1. 5.1 Graph Sketching
      1. 5.1.1 Definition of Sketch
      2. 5.1.2 Algorithm to Compute Sketch
      3. 5.1.3 Application of graph sketch
    2. 5.2 Layered Algorithm
      1. 5.2.1 Definition of Layered Algorithm
      2. 5.2.2 Application of layered algorithm
    3. 5.3 Summary
  7. 6 Future Work

###### List of Tables

  1. 5.1 Overview of the case-structure of min-cut of size $3$

###### List of Figures

  1. 3.1 Roadmap for finding small min-cuts
  2. 5.1 Different cases of min-cuts of size three
  3. (a) CASE-2 (Either of $\alpha$ or $\beta$ is 1 and the other is $0$)
  4. (b) CASE-3 (Either of $\alpha$ or $\beta$ is 1 and the other is $0$)
  5. (c) CASE-4 (Both $\alpha$ and $\beta$ are non-zero)
  6. (d) CASE-5 (At least two of $\alpha$, $\beta$ and $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$ are non-zero)
  7. (e) CASE-6 (at least two of $\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow})$, $\gamma({v_{3}}^{\downarrow},{v_{2}}^{\downarrow})$, $\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow})$ are non-zero)
  8. (f) CASE-7 (Both $\alpha$ and $\beta$ are non-zero)
  9. 5.2 Motivation for Sketching Technique in CASE-3
  10. 5.3 Motivation for Sketching Technique in CASE-7
  11. 5.4 Branching Number
  12. 5.5 Different types of sub-cases which occur when there exists a min-cut of size $3$ as in CASE-3
  13. 5.6 Two different non-isomorphic sub-cases of a min-cut as given by CASE-6
  14. (a) One of $\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$ is zero. WLOG let $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$
  15. (b) All three of $\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$ are non-zero
  16. 5.7 3-Sketch of different cases as viewed from node $v$
  17. 5.8 Reduced sketch ${\mathcal{S}}^{2}(v_{2},v_{3})$ when for some $v_{1},v_{2},v_{3}\in V\setminus r$ as in CASE-7
  18. 5.9 Min-cut of size $3$ as given by CASE-5

IITM | Indian Institute of Technology, Madras
---|---
TRSF | Tree Restricted Semigroup function

##  NOTATION

${v}^{\downarrow{T}}$ | set of descendants of vertex $v$ (including itself) in some tree $T$
---|---
$\mathcal{A}_{T}\left(v\right)$ | set of ancestors of vertex $v$ (including itself) in some tree $T$
$\pi_{{T}}\left(v\right)$ | parent of vertex $v$ in some tree $T$
$\operatorname{children}_{T}(v)$ | children of node $v$ in some tree $T$
$\delta(A)$ | cut set induced by vertex set $A$
$\eta_{T}(v)$ | $|\delta({v}^{\downarrow{T}})|$
$\gamma(A,B)$ |  $|\delta(A)\cap\delta(B)|$, where $A,B$ are vertex set
$\ell_{T}\left(v\right)$ | level of node $v$ in a rooted tree $T$, root at level $0$
$\alpha_{T}(x,l)$ | ancestor of vertex $x$ at level $l$
$R_{T}(v)$ | canonical tree of a node $v$ with respect to the spanning $T$
$\mathcal{S}_{T}^{k}(v)$ |  $k$-Sketch of node $v$ w.r.t a spanning tree $T$
$\mathcal{\xi}_{{T}}\left(v\right)$ | branching number of node $v$ w.r.t some tree $T$
${\mathcal{S}}_{T}^{k}(v,a)$ | reduced $k$-Sketch of a node $v$ and some $a\in{v}^{\downarrow{T}}\setminus v$ w.r.t a spanning tree $T$
$\rho_{T}(v)$ | a path from the root to node $v$ in the tree $T$
$\operatorname{LCA}_{T}(v_{1},v_{2})$ | Lowest Common Ancestor of two node $v_{1},v_{2}$ in some tree T
$\overline{\mathcal{N}}_{T}({A})$ | $\left\\{y\mid x\in A,y\notin A,(x,y)\in E,(x,y)\ \text{is a non-tree edge in tree }T\right\\}$
$\mathcal{P}_{T}(A)$ |  $\left\\{\rho_{T}(a)\mid a\in A\right\\}$

##  Chapter 1 Introduction

Networks of massive sizes are all around us. From large computer networks
which are the backbone of the Internet to sensor networks of any manufacturing
unit, the ubiquity of these networks is unquestionable. Each node in these
kinds of networks is an independent compute node or abstracted as one.
Further, nodes in these networks only have knowledge of their immediate
neighbors, but not the whole topology. There are many applications which
require us to solve problems related to such networks. To solve such problems,
a trivial idea is as follows: Each node sends its adjacency list to one
particular node through the underlying communication network; that node then
solves the required problem using the corresponding sequential algorithm. Such
an idea may not be cost effective due to the constraints of the capacity of
links and large sizes of these networks. The question then is: Does there
exist a faster cost-effective algorithm through which nodes in a network can
coordinate among each other to find the required network property? Such a
question is part of a more generalized spectrum of _Distributed Algorithms_.

In this thesis, we give fast distributed algorithm for finding small min-cuts.
An edge cut is the set of edges whose removal disconnects the network and the
one with a minimum number of edges is called as a _min-cut_. Finding small
min-cuts has applications in ensuring reliability and quality of service. This
enables the network administrator to know about the critical edges in the
network.

Our approach to finding the min-cut is based on our novel distributed
algorithmic techniques and backed by new characterizations of cuts and trees.
Our algorithmic techniques are as follows:

  * •

_Tree Restricted Semigroup Function_ wherein a semigroup function is computed
for each node in the network based on a rooted spanning tree

  * •

_Sketching Technique_ : which allows us to collect small but relevant
information of the network in a fast and efficient manner

  * •

_Layered Algorithm_ which finds min-cuts in smaller sub-graphs and
strategically uses the information to make the decision about min-cuts in the
complete graph.

###  1.1 Notations and Conventions

We consider an undirected, unweighted and simple graph $G=(V,E)$ where $V$ is
the vertex set and $E$ is the edge set. We use $n$ and $m$ to denote the
cardinalities of $V$ and $E$ respectively. Edges are the underlying physical
links and vertices are the compute nodes in the network. We will use the term
vertex and node interchangeably. Similarly, the terms edges and links will be
used interchangeably.

A cut $C=(A,V\setminus A)$, where $\emptyset\subsetneq A\subsetneq V$ is a
partition of the vertex set into two parts. The cut-set is the edges crossing
these two parts. A min-cut is a cut-set with a minimum number of edges. Let
$d_{G}(u,v)$ be the distance between any two nodes $u,v$ in the network which
is defined by the number of edges in the shortest path between them. We will
consider connected networks, so $d_{G}(u,v)$ is guaranteed to be well-defined
and finite. The diameter of the graph $G$ is defined as $\max\limits_{u,v\in
V}d_{G}(u,v)$. We will use $D$ to denote the diameter of the graph and $n$ for
the size of the vertex set and $m$ for the size of edge set.

In a typical communication network, the diameter $D$ is much smaller than the
number of vertices $n$. This is because the networks are often designed in
such a way that there is an assurance that a message sent from any node to any
other node should not be required to pass through too many links.

###  1.2 Distributed Model

Different types of communication networks have different parameters. This is
primarily based on how communication takes place between any two nodes in a
distributed system. For the algorithm designers, these details are hidden and
abstracted by appropriate modeling of the real world scenario. An established
book in this domain titled ‘Distributed Computing: A Locality-Sensitive
Approach’ [23] remarks: “ _The number of different models considered in the
literature is only slightly lower than the number of papers published in this
field_ ”. But certainly, over the years, the research community working around
this area have narrowed down to a handful of models. Out of them, the CONGEST
model has been quite prominent and captures several key aspects of typical
communication networks.

In the CONGEST model, as in most other distributed networks, each vertex acts
as an independent compute node. Two nodes may communicate to each other in
synchronous rounds only if they have a physical link between them. The message
size is restricted to $O(\log n)$ bits across each link in any given round. We
will focus our attention on communication which is more expensive than
computation.

In the CONGEST model, the complexity of an algorithm is typically measured in
terms of the number of rounds required for an algorithm to terminate.
Parallels of this could be drawn to the time complexity of sequential
algorithms. Much of the focus has been on the study of the distributed round
complexity of algorithms but recently there has been some renewed interest to
study the message complexity (the sum total of messages transmitted across all
edges) as well [22, 4]. Apart from these some recent research is also being
directed towards the study of asymptotic memory required at each node during
the execution of the algorithm [5]. In this thesis, we will limit our focus on
the analysis of round complexity.

###  1.3 Classification of network problems based on locality

Any problem pertaining to a communication network may depend either on local
information or global information. Local information of a node comprises
knowledge of immediate neighbors or nodes which are just a constant number of
hops away. Global information includes knowledge of nodes across the network.

One of the prominent examples of a problem which just requires local
information is of finding a _maximal independent set_ (MIS). An _independent
set_ is a set of vertices such that no two vertices in the set have an edge
between them. An MIS is an independent set such that no vertex can be added
into it without violating independence. It has been shown by [18] that finding
MIS requires $O(\log n)$ rounds.

On the other side, to gather global information at all nodes, it takes at
least $D$ rounds. This is because the farthest node could be as much as $D$
distance away. Thus the complexity of algorithms which require global
information is $\Omega(D)$.

Simple problems like finding the count of the number of nodes in the network,
constructing a BFS tree, leader election etc are problems which require global
information and takes $O(D)$ rounds. Apart from this, there are some problems
which require global information and have been proved to take at least
$\Omega(D+\sqrt{n})$ rounds. A prominent example is that of finding a Minimum
Spanning Tree (MST). It has been shown that to even find an approximate MST we
require $\Omega(D+\sqrt{n})$ rounds [3]. One of the key idea used in most of
the algorithms which take $O(D+\sqrt{n})$ is a result from [17], which gives a
distributed algorithm that can partition nodes of any spanning tree $T$ into
$O(\sqrt{n})$ subtrees such that each subtree has $O(\sqrt{n})$ diameter.
Basically, this approach can be considered as a classical divide and conquer
paradigm of distributed algorithms. To solve any problem using this idea,
nodes are divided into $O(\sqrt{n})$ clusters and then the problem is solved
in each of the clusters and subsequently, a mechanism is given to combine the
results.

###  1.4 Overview of past results

In this section, we will give an overview of the current progress in finding a
min-cut. A more detailed technical review of the relevant historical results
will be given in next chapter.

In the centralized setting, the problem of finding min-cut has seen a lot of
advances [11, 13, 12, 15, 20, 19, 6, 27, 14]. Recently, in the centralized
setting even a linear time algorithm have been proposed for finding min-cut by
[16] and further improved by [9].

A few attempts at finding min-cuts in the distributed setting (in the CONGEST
model in particular) have been made in past. These include work by [1, 29, 30,
24, 25, 21, 7]. A decade-old result by [25], currently stands out as the most
efficient way to find min-cut of small sizes in particular of size one. They
gave an $O(D)$ round algorithm using random circulation technique for finding
min-cuts of size $1$. Their result of finding a min-cut of size one has also
been extended to give a Las Vegas type randomized algorithms to find min-cut
of size 2 in $O(D)$ rounds. But a deterministic analogue of the same has so
far been elusive.

More recently [21] have given a
$O((\sqrt{n}\log^{*}n+D)k^{4}\log^{2}n)$111$\log^{*}n$ (usually read ”log
star”), is the number of times the logarithm function must be iteratively
applied before the result is less than or equal to $1$ rounds algorithm to
find min-cut of size $k$. There have also been results to find an approximate
min-cut. [8] gave a distributed algorithm that, for any weighted graph and any
$\epsilon\in(0,1)$, with high probability finds a cut of size at most
$O(\epsilon^{-1}k)$ in $O(D)+\tilde{O}(\sqrt{n})$ 222$\widetilde{O}$ hides
logarithmic factors rounds, where $k$ is the size of the minimum cut. [21]
improves this aproximation factor and give a $(1+\epsilon)$ approximation
algorithm in $O((\sqrt{n}\log^{*}n+D)\epsilon^{-5}\log^{3}n)$ time. Also, [7]
have given a min-cut algorithm for planar graphs which finds a $(1-\epsilon)$
approximate min-cut in $\widetilde{O}(D)$ rounds.

While a linear time algorithm for finding min-cut exists in the centralized
setting, in distributed setting the best known exact algorithm still takes
$O((\sqrt{n}\log^{*}n+D)k^{4}\log^{2}n)$ rounds to deterministically find a
min-cut of size $k>1$. Moreover, a $\widetilde{O}(D)$ round algorithm exists
to find a min-cut in planar graphs. The following question arises: Is
$\Omega(\sqrt{n}+D)$ a lower bound for finding min-cuts or can we save the
large factor of $\sqrt{n}$ as known for planar graphs for at least the small
min-cuts. We answer this question through our thesis. We present a new
algorithm to deterministically find all the min-cuts of size one, two, and
three. For min-cut of size either one or two our algorithm takes $O(D)$
rounds. For min-cuts of size three our algorithm takes $O(D^{2})$ rounds.

###  1.5 Organization of this thesis

In Chapter 2, we will survey simple distributed algorithms for the CONGEST
model and also review graph properties like the cuts spaces and cycle spaces.
We also give a brief overview of previously know techniques to find min-cut in
distributed setting, in particular the techniques based on greedy tree packing
and random circulations.

In Chapter 3, we will present our characterization of trees and cuts. Here we
will also give a road-map of the novel distributed techniques introduced in
this thesis. In Chapter 4 and Chapter 5, we will present distributed
algorithms which will ensure that whenever there exists a min-cut of the kind
the required quantities by our charecterization will be communicated to at
least one node in network. In Chapter 4, we introduce _Tree Restricted
Semigroup Function_ and show that this is enough for finding min-cuts of size
$1$ and $2$ optimally. Further, in Chapter 5, we will introduce two new
techniques: _Sketching_ and _Layered Algorithm_ to find min-cuts of size $3$.

##  Chapter 2 Preliminaries and Background

In this chapter, we will review fundamental network algorithms in the
distributed setting. Among the distributed algorithms, we will discuss the
construction of various types of spanning trees including Breadth First Search
(BFS) Tree, Depth First Search (DFS) tree and Minimum Spanning Tree (MST).
Further, we will discuss some simple tree based algorithmic paradigms
generally used in distributed networks. We also review important and relevant
concepts like cut spaces and cycle spaces and show that these are vector
spaces and orthogonal to each other. Finally, we will survey two important
recent techniques used to find min-cuts in distributed networks.

###  2.1 Simple algorithms in Distributed Networks

As mentioned in the earlier chapter, we use the CONGEST model of distributed
networks which considers point-to-point, synchronous communications between
any two nodes in a network. In any given synchronous round, communication is
only allowed between nodes with a physical link and is restricted to $O(\log
n)$ bits.

The network will be modeled as a simple undirected graph $G=(V,E)$. As stated
earlier, we will use $n$ to denote the number of nodes, $m$ to denote the
number of edges and $D$ as the diameter of the network. Each node in this
network has a unique $id$ which is of size $O(\log n)$ bits. Whenever we say
node $x$ in the network, we mean a node with $x$ as its $id$.

Various algorithms in distributed setting start with constructing a tree. A
tree gives structure to the problem by defining a relationship between nodes
as decedents or as ancestors or neither of them. Moreover, it also serves as a
medium for information flow between nodes in a structured way using the tree
edges. In this section, we state results about the construction of various
types of spanning trees and review simple distributed algorithms on trees.

####  2.1.1 Tree Constructions and Notations

Let ${T}$ be any spanning tree rooted at node $r_{T}$ (or just $r$ when clear
from the context). Let $\ell_{T}\left(x\right)$ be the level of node $x$ in
$T$ such that the root $r$ is at level $0$ and for all other nodes $x$,
$\ell_{T}\left(x\right)$ is just the distance from root following the tree
edges. For $x\neq r$, let $\pi_{{T}}\left(x\right)$ denote the parent of the
vertex $x$ in $T$. For every node $v$, let $\operatorname{children}_{T}(v)$ be
the set of children of $v$ in the tree $T$. Further for any node $v$, we will
use $\mathcal{A}_{T}\left(v\right)$ to denote the set of all ancestors of node
$v$ in tree $T$ including $v$ and ${v}^{\downarrow{T}}$ as the set of vertices
which are descendants of $v$ in the tree $T$ including $v$. We will briefly
review construction of different types of trees. For details the reader is
referred to [23].

##### BFS Tree.

Our approach to find min-cuts uses an arbitrary BFS tree. Although, our
technique is invariant of the type of the spanning tree chosen but a BFS tree
is ideal because it can be constructed in just $O(D)$ rounds. The following
lemma states the guarantees regarding construction of a BFS trees

######  Lemma 2.1.

There exists a distributed algorithm for construction of a BFS tree which
requires at most $O(D)$ rounds.

A brief description of an algorithm to construct BFS tree as follows: an
arbitrary node $r$ initiates the construction of BFS tree, it assigns itself a
level $\ell\left(r\right)=0$. Then the node $r$ advertises to all its adjacent
neighbors about its level, who then joins the BFS tree at level $1$ as
children of $r$. Subsequently, each node at level $1$ also advertises its
level to all its neighbors, but only those nodes join the BFS tree as children
of nodes at level $1$ who are not part of the BFS tree already. Here, ties are
broken arbitrarily. This process goes on until all the nodes are part of the
BFS tree.

##### DFS Tree.

Unlike BFS tree, the depth of a DFS tree is oblivious of the diameter. In
fact, two of the early approaches to find cut edges in distributed networks
used a DFS tree [10, 1]. The following lemma states the guarantees regarding
construction of a DFS trees.

######  Lemma 2.2.

There exists a distributed algorithm for construction of a DFS tree which
requires at most $O(n)$ rounds.

##### MST Tree.

The following lemma is known regarding the complexity to construct an MST
tree. In fact, it is also known that we cannot do better in terms of round
complexity for construction of the MST tree. [3].

######  Lemma 2.3.

For a weighted network, there exists a distributed algorithm for construction
of MST tree which requires $O(\sqrt{n}+D)$ rounds.

A recent technique to find min-cuts given by [21] assigns weights to each edge
in an unweighted graph and compute MST tree, further these weights are updated
and a new MST tree is constructed. This goes on for $\text{polylog }n$
iterations. We review this technique in Section 2.3.

####  2.1.2 Convergecast and Broadcast

We will now give brief details about simple distributed algorithms. In
particular, we will describe _Broadcasts_ and _Convergecasts_. These are
mechanisms to move data along the edges of any fixed tree. In this thesis, we
will often use these techniques to compute properties of the given network
which will, in turn, help us to find min-cuts.

##### Convergecasts

In distributed network algorithms, there are applications where it is required
to collect information upwards on some tree, in particular, this is a flow of
information from nodes to their ancestors in the tree. This type of a
technique is called as _Convergecast_. In a BFS tree $T$, any node has at most
$D$ ancestors, but for any node $v$ the number of nodes in descendants set
${v}^{\downarrow{T}}$ is not bounded by $D$. Thus during convergecast, all
nodes in the set ${v}^{\downarrow{T}}$ might want to send information upwards
to one of the ancestor node $v$. This may cause a lot of contentions and is a
costly endeavor. In this thesis, whenever we use a covergecast technique, we
couple it with either an _aggregation based strategy_ or a _contention
resolution mechanism_.

In an aggregation based strategy, during covergecast, the flow of information
from nodes at a deeper level is synchronized and aggregated together to be
sent upwards. In Chapter 4, we introduce _tree restricted semigroup function_
which is such an aggregation based technique. Moreover, our algorithm to
compute the specially designed _Sketch_ also uses this kind of
convergecasting. Further, in a contention resolution mechanism, only certain
information are allowed to move upwards based on some specific criteria, thus
limiting contention. In Chapter 5, we use such contention resolution mechanism
to convergecast details found by our _Layered Algorithm_.

##### Broadcasts

In this technique, the flow of information takes place in the downward
direction along the tree edges. When such an information is aimed to be
communicated to all the nodes in the decedent set then it is called
_broadcast_. In the general broadcast algorithm, for some spanning tree $T$,
the root is required to send a message of size $O(\log n)$ bits to all the
nodes. We state the following lemma from [23] whose proof uses a simple
flooding based algorithm.

######  Lemma 2.4 (Lemma 3.2.1 from [23]).

For any spanning tree $T$, let the root have a message of size $O(\log n)$
bits, then it can be communicated to all the nodes in $O(Depth(T))$ rounds.

###### Proof.

Here we assume that there exists a spanning tree $T$ and each node is aware of
the spanning tree edges incident to it. Now, all we need is to flood the
message to the entire tree. In the first round, the root sends this message to
all its children, who are at level $1$. Further, in the second round, nodes at
level $1$ sends the message to all their children who are at level $2$ and so
on. Thus, in all, we will require $O(Depth(T))$ rounds. ∎

At various stages of the algorithms presented in this thesis, we require two
variants of the general broadcast techniques. They are described below. We
also give the respective algorithm for them in Lemma 2.5.

  1. _Broadcast Type-1_

Given a spanning tree $T$, all nodes $v\in V$ have a message of size $O(\log
n)$ bits which is required to be communicated to all the nodes in the vertex
set ${v}^{\downarrow{T}}$.

  2. _Broadcast Type-2_

Given a spanning tree $T$, all nodes $v\in V$ have $Depth(T)$ messages of size
$O(\log n)$ bits which is required to be communicated to all the nodes in the
vertex set ${v}^{\downarrow{T}}$.

######  Lemma 2.5.

There exist distributed algorithms which require $O(Depth(T))$ and
$O(Depth(T)^{2})$ rounds respectively for Broadcast Type-1 and Broadcast
Type-2.

###### Proof.

First, let us consider _Broadcast Type-1_. Here we will use Lemma 2.4 coupled
with _pipelining_. Each node $v$ initiates a broadcast of its $O(\log n)$ bits
sized message to the subtree rooted at node $v$. using the algorithm from
Lemma 2.4 in the first round. If $v$ is not the root of the spanning tree,
then in the first round it will have received the message broadcasted by its
parent and it is imperative to node $v$ to send this message to all its
children. Note that this does not hinder with the broadcast initiated by node
$v$ to the subtree rooted at it. In all the subsequent rounds a train of
messages is _pipelined_ one after another through the tree edges, enabling
broadcasts initiated by nodes to run without any hindrance or congestion. Thus
it only takes $O(Depth(T))$ rounds for this type of broadcast. For _Broadcast
Type-2_ , we just need to run $Depth(T)$ iterations of _Broadcast Type-1_
taking $O(Depth(T)^{2})$ rounds. ∎

###  2.2 Cuts Space and Cycle Space

In this section, we will discuss about the _cut space_ and _cycle spaces_. We
will first define _cut spaces_ , _cycle spaces_ and prove that, they are
vector spaces. Further, we will show that they are orthogonal. All these facts
are well known and have been part of standard graph theory books, for example,
see [2].

As defined earlier, $E$ and $V$ are edge set and vertex set respectively. We
will work with the field $\mathbb{Z}_{2}$ and the space
$\mathbb{Z}_{2}^{|E|}$. Let $S\subseteq E$, then its characteristics vector is
defined as follows: $\chi_{e}^{S}=1$ (at coordinate $e$) for $e\in S$ and
$\chi_{f}^{S}=0$ for $f\notin E$. Here we will use the operator $\oplus$
(symmetric difference or XOR) for the space $\mathbb{Z}_{2}^{|E|}$. Let
$R,S\subseteq E$. Note that $R,S$ are edge sets whereas $\chi^{R}$ and
$\chi^{S}$ are binary vectors in $\mathbb{Z}_{2}^{|E|}$. When we use $R\oplus
S$, we will mean symmetric difference of the two sets and when we use
$\chi^{R}\oplus\chi^{S}$, we will mean XOR operation between the two vectors.
It is easy to see that $\chi^{R}\oplus\chi^{S}=\chi^{R\oplus S}$

Let $\phi\subseteq E$. If the subgraph $(V,\phi)$ has all the vertex with even
degrees then $\phi$ is a _binary circulation_. The set of all binary
circulations of a graph is called the _cycle space_ of the graph. Similarly,
let $A\subseteq V$. Define an induced cut $\delta(A)$ as the set of edges with
exactly one endpoint in $A$ or essentially the cut set $(A,V\setminus A)$. The
set of all the induced cuts is called the _cut space_ of the graph.

######  Theorem 2.6.

The cut space and cycle space are vector spaces of $\mathbb{Z}_{2}^{|E|}$

###### Proof.

To show that both the structures are vector spaces it is sufficient to show
that there exists a $0$ for the vector space, an addition operator and inverse
of each element. We will show that $\emptyset_{E}$ is the required $0$ of the
vector space and $\oplus$ is the operator. For cut space take a set
$A=\emptyset$. Then $\delta(A)=\emptyset_{E}$ that is
$\chi^{\delta(A)}=\vec{0}_{2}$. Similarly for cycle space if take
$\phi=\emptyset\subset E$ then all the vertex in the graph $(V,\phi)$ have
degree as $0$ which is even. Let $A,B\subseteq V$. Then $\delta(A)$ and
$\delta(B)$ are induced cut defined for A,B. Let $A\oplus B$ be the symmetric
difference of the set $A$ and $B$. As per the definition $\delta(A)$ is the
set of edges which have exactly one end in $A$ and similarly for $\delta(B)$
which are the edges with one end in $B$. Now $A\oplus B$ is a symmetric
difference between the set $A,B$ and $\delta(A\oplus B)$ is the set of edges
with one end in $A\oplus B$. To see that $\delta(A)\oplus\delta(B)$ is equal
to $\delta(A\oplus B)$ just take two cases where $A\cap B=\emptyset$ and
$A\cap B\not=\emptyset$.

Now let us turn our attention to the cycle space. Let $R,S\subseteq E$. And
let $G_{1}=(V,R)$ and $G_{2}=(V,S)$ be two sub-graphs such that all vertices
are of even degrees in them; that is both $R,S$ are binary circulations. Now
consider the subgraph $G_{1,2}=(V,R\oplus S)$ and a vertex $v\in V$. The
degree of vertex $v$ in $G_{1,2}$ is $\deg_{R}(v)+\deg_{S}(v)-2\deg_{R\cap
S}(v)$ which is even. Hence $R\oplus S$ is also a binary circulation. ∎

The following corollary will be useful for proving our characterization of
cuts and trees given in Chapter 3.

######  Corollary 2.7.

Let $A_{1},A_{2},\ldots,A_{j}$ be set of vertices such that $\forall i\
A_{i}\subset V$ then $\delta(A_{1}\oplus A_{2}\oplus\ldots\oplus
A_{j})=\delta(A_{1})\oplus\delta(A_{2})\oplus\ldots\oplus\delta(A_{j})$

######  Theorem 2.8.

The cut space and cycle space are orthogonal.

###### Proof.

Let $A\subset V$ and $\phi$ be a binary circulation. Let $\chi^{\phi}$ and
$\chi^{\delta(A)}$ be the vectors corresponding to the $\phi$ and induced cut
$\delta(A)$. We have to show that $\chi^{\delta(A)}.\chi^{\phi}=0\left(\mod
2\right)$ which is equivalent to showing that
$|\chi^{\phi}\cap\chi^{\delta(A)}|$ is even. Now $\sum_{a\in
A}\deg_{\phi}(a)=\sum_{a\in A}|\phi\cap\delta(a)|$. Observe that
$\sum_{a}\deg_{\phi}(a)$ is even because $\phi$ is a binary circulation.
Further $\sum_{a\in A}|\phi\cap\delta(a)|$ counts the edges with both ends in
$A$ twice and every edge in $|\phi\cap\delta(A)|$ once and does not count any
other edge. Hence $|\phi\cap\delta(A)|$ is even. ∎

###  2.3 Min-Cuts in Distributed Networks

In this section we will review some past results for finding min-cuts, in
particular, the ideas employed in two recent works [26, 21]. While [21] relied
on greedy tree packing introduced by [28]; [26] gave a novel technique of
random circulations.

####  2.3.1 Using Greedy Tree Packing

First, we will define the concept of greedy tree packing. A _tree packing_
$\mathbb{T}$ is a multiset of spanning trees. Let the load of any edge $e$
w.r.t a tree packing $\mathbb{T}$, denoted by $\mathcal{L}^{\mathbb{T}}(e)$,
be defined as the number of trees in $\mathbb{T}$ containing $e$. A tree
packing $\mathbb{T}=\left\\{T_{1},\ldots,T_{j}\right\\}$ is greedy if each
$T_{i}$ is a minimum spanning tree (MST) with respect to the loads induced by
$\left\\{T_{1},\ldots,T_{i-1}\right\\}$. [28] has given the following results
related to tree packing:

######  Theorem 2.9 ([28]).

Let $G=(V,E)$ be an unweighted graph. Let $m$ be the number of edges in $G$
and $k$ be the size of min-cut. Then a greedy tree-packing with
$\omega(k^{7}\log^{3}m)$ contains a tree crossing some min-cut exactly once.

Based on the above theorem, [21] construct a greedy tree packing of
$\omega(k^{7}\log^{3}m)$ trees. There is a well-known algorithm to find MST in
$O(D+\sqrt{n})$ rounds. Further, in each tree, the authors find the size of
the smallest edge cut which shares only one edge with the tree. They give an
algorithm to do the same in $O(D+\sqrt{n})$ rounds for each tree. Note that
they cannot find all the min-cuts because of the limitations of Theorem 2.9
which only guarantees that there will exists some (but not all) min-cut which
will share exactly one edge with at least one tree in tree packing
$\mathbb{T}$.

####  2.3.2 Using Random Circulations

The random circulation technique has its foundation based on a well-known fact
that cut spaces and cycle spaces are orthogonal to each other [2]. Based on
this technique [25] gave the following result

######  Theorem 2.10 ([25]).

There is a Las Vegas distributed algorithm to compute all the min-cuts of size
1 and 2 (cut edges and cut pairs) in $O(D)$ time.

The above result cannot be made deterministic for min-cuts of size 2. Moreover
extending the random circulation technique for min-cuts of size $3$ or more do
not seem plausible due to its fundamental limitations. But as shown in [24],
1-cuts can be found deterministically in $O(D)$ rounds.

##  Chapter 3 Technical Overview

We give deterministic algorithm for finding min-cuts of size one, two, and
three. We find the min-cut of size one and two in $O(D)$ time and of size
three in $O(D^{2})$ time. We recreate the optimal result for min-cut of size
one. For min-cuts of size two and three our results resolve the open problem
from [26]. We give a new characterization involving trees and min-cuts. We
also introduce a new algorithmic technique named as the Tree restricted
Semigroup function (TRSF) which is defined with respect to a tree $T$. The
TRSF is a natural approach to find min-cuts of size one. We also show a non-
trivial application of TRSF in finding min-cuts of size two, which is quite
intriguing. For finding, if there exists a min-cut of size $3$ we introduce a
new _sketching technique_ where each node finds a view of the graph with
respect to a tree by getting rid of edges which may not be a part of a min-
cut. The sketching idea coupled with our characterization results helps us to
find the required min-cut.

###  3.1 Characterization of Trees and Cuts

In this subsection, we establish some fundamental relationships between trees
and cuts which will help us find the required min-cuts. When a min-cut shares
$k$ edges with a spanning tree then we say that it $k$-respects the tree. Each
min-cut will at least share one edge with a spanning tree otherwise the said
min-cut will not be a cut because there will exist a spanning tree which
connects all the nodes. We give the following simple observation in this
regard.

######  Observation 3.1.

For any induced cut of size k and a spanning tree $T$, there exists some
$j\in[1,\min(k,n)]$ such that induced cut $j-$ respects the tree $T$.

The above simple observation lets us break the problem of finding small min-
cuts into different cases. A min-cut of size $1$ will always share one edge
with any spanning tree. A min-cut of size $2$ shares either $1$ or $2$ edges
with any spanning tree. Similarly a min-cut of size $3$ either shares $1,2$ or
$3$ edges with any spanning tree.

We now make a simple observation along with a quick proof sketch

######  Observation 3.2.

When an induced cut of size $k$ 1-respects a spanning tree $T$, then there
exists at least one node $v$ such that $|\delta({v}^{\downarrow{T}})|=k$.

###### Proof Sketch.

Consider the cut edge $(u,v)$ that is in $T$ with $u$ being closer to the root
$r_{T}$. Since the tree only 1-respects the cut, ${v}^{\downarrow{T}}$ remains
on one side of the cut, while $r_{T}$ is on the other. Moreover,
$V\setminus{v}^{\downarrow{T}}$ fully remains on the side with $r_{T}$;
otherwise, $T$ will not be limited to 1-respecting the cut. Thus,
${v}^{\downarrow{T}}$ will serve our required purpose. ∎

We will now give a distributed algorithm such that each node $v$ finds
$|\delta({v}^{\downarrow{T}})|$ in $O(D)$ rounds. For the remaining cases, we
will give lemmas to characterize the induced cuts and tree. These
characterizations follow from Corollary 2.7. We begin with the
characterization of an induced cut of size 2 when it 2-respects a tree $T$.

######  Lemma 3.3 (2-cut, 2-respects a spanning tree $T$).

Let $T$ be any spanning tree. When $u\neq v$ and $u,v\in V\setminus r$. Then
the following two statements are equivalent.

  1. $P_{1}:$

$\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}$ is
a cut set induced by ${{u}^{\downarrow{T}}}\oplus{{v}^{\downarrow{T}}}$.

  2. $P_{2}:$

$|\delta({u}^{\downarrow{T}})|=|\delta({v}^{\downarrow{T}})|=|\delta({u}^{\downarrow{T}})\cap\delta\left({v}^{\downarrow{T}}\right)|+1$.

To prove the above lemma the following simple observation will be helpful.

######  Observation 3.4.

For any $u\neq v$ and $u,v\in V\setminus r$, and a spanning tree $T$ the edge
$(\pi_{{T}}\left(v\right),v)\in\delta({{v}^{\downarrow{T}}})$ but
$(\pi_{{T}}\left(v\right),v)\notin\delta({{u}^{\downarrow{T}}})$; also
$(\pi_{{T}}\left(u\right),u)\in\delta({{u}^{\downarrow{T}}})$ but
$(\pi_{{T}}\left(u\right),u)\notin\delta({{v}^{\downarrow{T}}})$.

###### Proof.

Consider the given spanning tree $T$. Here the edge
$(\pi_{{T}}\left(u\right),u)$ has one end in the vertex set
${u}^{\downarrow{T}}$ and the other end in the vertex set
$V\setminus{u}^{\downarrow{T}}$. Thus the edge $(u,\pi_{{T}}\left(u\right))$
is part of the cut set
$({u}^{\downarrow{T}},V\setminus{u}^{\downarrow{T}})=\delta({u}^{\downarrow{T}})$.
Now, consider any other node $v$. Either $v\in{u}^{\downarrow{T}}$ or it does
not. Let’s take the first case when $v\in{u}^{\downarrow{T}}$. Since $v\neq
u$, thus both the end points of the edge $(\pi_{{T}}\left(u\right),u)$ are
outside the set ${v}^{\downarrow{T}}$ hence
$(\pi_{{T}}\left(u\right),u)\notin\delta({v}^{\downarrow{T}})$.

When $v\notin{u}^{\downarrow{T}}$, then also similar argument holds. If
$v\in\mathcal{A}_{T}\left(u\right)$, then both the endpoints are in the set
${v}^{\downarrow{T}}$, otherwise both of them are outside the set
${v}^{\downarrow{T}}$. In either of them the edge
$(\pi_{{T}}\left(u\right),u)\notin\delta({v}^{\downarrow{T}})$. ∎

###### Proof of Lemma 3.3.

Consider the forward direction,
$\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}$ is
a cut set induced by ${{u}^{\downarrow{T}}}\oplus{{v}^{\downarrow{T}}}$.
Therefore
$\delta({{v}^{\downarrow{T}}}\oplus{{u}^{\downarrow{T}}})=\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}$.
Further from Corollary 2.7, we have
$\delta({{v}^{\downarrow{T}}}\oplus{{u}^{\downarrow{T}}})=\delta({{u}^{\downarrow{T}}})\oplus\delta({{v}^{\downarrow{T}}})$.
Therefore
$\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}=\delta({{u}^{\downarrow{T}}})\oplus\delta({{v}^{\downarrow{T}}})$
which along with Observation 3.4 implies that
$\delta({{u}^{\downarrow{T}}})\setminus(\pi_{{T}}\left(u\right),u)=\delta({{v}^{\downarrow{T}}})\setminus(\pi_{{T}}\left(v\right),v)$
thus
$|\delta({{v}^{\downarrow{T}}})|-1=|\delta({{v}^{\downarrow{T}}})\cap\delta({{u}^{\downarrow{T}}})|$
and
$|\delta({{u}^{\downarrow{T}}})|-1=|\delta({{v}^{\downarrow{T}}})\cap\delta({{u}^{\downarrow{T}}})|$.

For the other direction, given that
$|\delta({{u}^{\downarrow{T}}})\cap\delta({{v}^{\downarrow{T}}})|+1=|\delta({{v}^{\downarrow{T}}})|=|\delta({{u}^{\downarrow{T}}})|$,
which along with Observation 3.4 implies that
$\delta({{u}^{\downarrow{T}}})\setminus(\pi_{{T}}\left(u\right),u)=\delta({{v}^{\downarrow{T}}})\setminus(\pi_{{T}}\left(v\right),v)$.
Hence
$\delta({{u}^{\downarrow{T}}})\oplus\delta({{v}^{\downarrow{T}}})=\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}$.
Using the fact that
$\delta({{v}^{\downarrow{T}}})\oplus\delta({{u}^{\downarrow{T}}})=\delta({{v}^{\downarrow{T}}}\oplus{{u}^{\downarrow{T}}})$,
the edge set
$\left\\{(\pi_{{T}}\left(u\right),u),(\pi_{{T}}\left(v\right),v)\right\\}$ is
a cut induced by ${{v}^{\downarrow{T}}}\oplus{{u}^{\downarrow{T}}}$. ∎

When an induced cut of size $2$, 2-respects a spanning tree there could be two
sub-cases. Consider nodes $u,v$ as in the above lemma. Here either
${u}^{\downarrow{T}}\cap{v}^{\downarrow{T}}=\emptyset$ or
${u}^{\downarrow{T}}\subseteq{v}^{\downarrow{T}}$ (which is same as
${v}^{\downarrow{T}}\subseteq{u}^{\downarrow{T}}$). The above lemma unifies
these two cases. In the next chapter, we will show that how one of the nodes
in the network finds all the three quantities as required by the above lemma
when there exists a min-cut of this kind.

Now we will see the similar characterizations for an induced cut of size 3
when it 2 respects the cut and 3-respects the cut.

######  Lemma 3.5 (3-cut, 2-respects a spanning tree $T$).

Let $T$ be any tree. Let $v_{1},v_{2}\in V\setminus r$ be two different nodes
and $e$ be a non-tree edge, then the following two are equivalent.

  1. $P_{1}:$

$\left\\{(\pi_{{T}}\left(v_{1}\right),v_{1}),(\pi_{{T}}\left(v_{2}\right),v_{2}),e\right\\}$
is a cut set induced by the vertex set
${v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}$.

  2. $P_{2}:$

$|\delta({v_{1}}^{\downarrow{T}})|-2=|\delta({v_{2}}^{\downarrow{T}})|-1=\gamma({{v_{1}}^{\downarrow{T}}},{{v_{2}}^{\downarrow{T}}})$
or
$\delta({v_{1}}^{\downarrow{T}})-1=|\delta({v_{2}}^{\downarrow{T}})|-2=\gamma({{v_{1}}^{\downarrow{T}}},{{v_{2}}^{\downarrow{T}}})$.

###### Proof.

The proof is similar to Lemma 3.3. Consider the forward direction,
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a cut set induced by ${{v_{1}}^{\downarrow}}\oplus{{v_{2}}^{\downarrow}}$.
Therefore
$\delta({{v_{2}}^{\downarrow}}\oplus{{v_{1}}^{\downarrow}})=\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$.
Further from Corollary 2.7, we have
$\delta({{v_{1}}^{\downarrow}}\oplus{{v_{2}}^{\downarrow}})=\delta({{v_{1}}^{\downarrow}})\oplus\delta({{v_{2}}^{\downarrow}})$.
Therefore
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}=\delta({{v_{1}}^{\downarrow}})\oplus\delta({{v_{2}}^{\downarrow}})$.
Since $e\in\delta({v_{1}}^{\downarrow})\oplus\delta({v_{2}}^{\downarrow})$.
Thus $e\in\delta({v_{1}}^{\downarrow})$ or $e\in\delta({v_{2}}^{\downarrow})$
but not in both due to the symmetric difference operator. Without loss in
generality, let $e\in\delta({v_{1}}^{\downarrow})$. Now Observation 3.4
implies that
$\delta({{v_{1}}^{\downarrow}})\setminus\left\\{(\pi\left(v_{1}\right),v_{1}),e\right\\}=\delta({{v_{2}}^{\downarrow}})\setminus(\pi\left(v_{2}\right),v_{2})$
thus
$|\delta({{v_{1}}^{\downarrow}})|-2=|\delta({{v_{2}}^{\downarrow}})\cap\delta({{v_{2}}^{\downarrow}})|$
and
$|\delta({{v_{2}}^{\downarrow}})|-1=|\delta({{v_{1}}^{\downarrow}})\cap\delta({{v_{2}}^{\downarrow}})|$.
Similarly when $e\in\delta({v_{2}}^{\downarrow})$ then
$|\delta({{v_{1}}^{\downarrow}})|-1=|\delta({{v_{2}}^{\downarrow}})\cap\delta({{v_{2}}^{\downarrow}})|$
and
$|\delta({{v_{2}}^{\downarrow}})|-2=|\delta({{v_{1}}^{\downarrow}})\cap\delta({{v_{2}}^{\downarrow}})|$

For the other direction, without loss in generality, let us choose one of the
two statements. In particular, let
$|\delta({{v_{1}}^{\downarrow}})\cap\delta({{v_{2}}^{\downarrow}})|=|\delta({{v_{1}}^{\downarrow}})|-1=|\delta({{v_{2}}^{\downarrow}})|-2$,
which along with Observation 3.4 implies that
$|\delta({{v_{1}}^{\downarrow}})\setminus(\pi\left(v_{1}\right),v_{1})|=|\delta({{v_{2}}^{\downarrow}})\setminus(\pi\left(v_{2}\right),v_{2})|-1$.
Thus there exists exactly one edge $e$ which is not in
$\delta({v_{1}}^{\downarrow})$ but in $\delta({v_{2}}^{\downarrow})$ Hence
$\delta({{v_{1}}^{\downarrow}})\oplus\delta({{v_{2}}^{\downarrow}})=\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$.
Using the fact that
$\delta({{v_{2}}^{\downarrow}})\oplus\delta({{v_{1}}^{\downarrow}})=\delta({{v_{2}}^{\downarrow}}\oplus{{v_{1}}^{\downarrow}})$;
the edge set
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a cut induced by ${{v_{1}}^{\downarrow}}\oplus{{v_{2}}^{\downarrow}}$. ∎

######  Lemma 3.6 (3-cut, 3-respects a spanning tree $T$).

Let $T$ be any tree. Let $v_{1},v_{2},v_{3}\in V\setminus r$, further each of
$v_{1},v_{2}$ and $v_{3}$ are different then the following two statements are
equivalent:

  1. $P_{1}:$

$\left\\{(v_{1},\pi_{{T}}\left(v_{1}\right)),(v_{2},\pi_{{T}}\left(v_{2}\right)),(v_{3},\pi_{{T}}\left(v_{3}\right))\right\\}$
is a cut-set induced by
${v_{1}}^{\downarrow{T}}\oplus{v_{2}}^{\downarrow{T}}\oplus{v_{3}}^{\downarrow{T}}$.

  2. $P_{2}:$

$|\delta({v_{i}}^{\downarrow{T}})|-1=\sum\limits_{j\in\left\\{1,2,3\right\\}\setminus\left\\{i\right\\}}\gamma({v_{i}}^{\downarrow{T}},{v_{j}}^{\downarrow{T}}),\
\forall i\in\left\\{1,2,3\right\\}$.

###### Proof.

Consider the forward direction $\delta({v_{1}}^{\downarrow}\ \oplus\
{v_{2}}^{\downarrow}\ \oplus\
{v_{3}}^{\downarrow})=\\{(v_{1},\pi\left(v_{1}\right)),(v_{2},\pi\left(v_{2}\right)),$
$(v_{3},\pi\left(v_{3}\right))\\}$. Also, by Corollary 2.7, we know that
$\delta({v_{1}}^{\downarrow})\oplus\delta({v_{2}}^{\downarrow})\oplus\delta({v_{3}}^{\downarrow})=\delta({v_{1}}^{\downarrow}\oplus{v_{2}}^{\downarrow}\oplus{v_{3}}^{\downarrow})$.
Notice that there are 3 equations in $P_{2}$ when $i\in[1,3]$. We will show
for $i=1$ and the argument for the rest will follow similarly. For all edge
$e\neq(v_{1},\pi\left(v_{1}\right))$ and $e\in\delta({v_{1}}^{\downarrow})$
then $e$ must be present exactly once in either of
$\delta({v_{2}}^{\downarrow})$ or $\delta({v_{3}}^{\downarrow})$. Because if
it is present in none of them then among the three sets
$\delta({v_{1}}^{\downarrow}),\delta({v_{2}}^{\downarrow})$ and
$\delta({v_{3}}^{\downarrow})$, $e$ is exactly in one that is
$\delta({v_{1}}^{\downarrow})$. Thus
$e\in\delta({v_{1}}^{\downarrow}\oplus{v_{2}}^{\downarrow}\oplus{v_{3}}^{\downarrow})$
which is not true. Also if it is present in both
$\delta({v_{2}}^{\downarrow})$ and $\delta({v_{3}}^{\downarrow})$ then
similarly
$e\in\delta({v_{1}}^{\downarrow}\oplus{v_{2}}^{\downarrow}\oplus{v_{3}}^{\downarrow})$,
which again is not true. Thus apart from the edge
$(\pi\left(v_{1}\right),v_{1})$ whenever there exists an
$e\in\delta({v_{1}}^{\downarrow})$ then it is also present in exactly one of
$\delta({v_{2}}^{\downarrow})$ or $\delta({v_{3}}^{\downarrow})$. Thus
$|\delta({v_{1}}^{\downarrow})|-1=|\delta({v_{1}}^{\downarrow})\cap\delta({v_{2}}^{\downarrow})|+|\delta({v_{1}}^{\downarrow})\cap\delta({v_{3}}^{\downarrow})|$.

For the backward direction, we will again focus our attention to three
different edge sets
$\delta({v_{1}}^{\downarrow}),\delta({v_{2}}^{\downarrow})$ and
$\delta({v_{3}}^{\downarrow})$. We know that the edge
$(\pi\left(v_{1}\right),v_{1})\in\delta({v_{1}}^{\downarrow})$ but not in
either of $\delta({v_{2}}^{\downarrow})$ and $\delta({v_{3}}^{\downarrow})$. 3
Similarly for $(\pi\left(v_{2}\right),v_{2})$ and
$(\pi\left(v_{3}\right),v_{3})$. Lets the edge set
$C=\delta({v_{1}}^{\downarrow})\oplus\delta({v_{2}}^{\downarrow})\oplus\delta({v_{3}}^{\downarrow})$.
Thus $C$ is sure to contain the edges
$(v_{1},\pi\left(v_{1}\right)),(v_{2},\pi\left(v_{2}\right))$ and
$(v_{3},\pi\left(v_{3}\right))$ because of the symmetric difference operator
between the three sets. Now based on the condition in $P_{2}$ we will show
that there is no other edge $e$ in $C$. Imagine there is only one edge
$e\neq(\pi\left(v_{1}\right),v_{1})$ and $e\in\delta({v_{1}}^{\downarrow})$
and $e\in C$. Thus $e$ could either be in both $\delta({v_{2}}^{\downarrow})$
and $\delta({v_{3}}^{\downarrow})$ or none of them. Imagine $e$ is in both
$\delta({v_{2}}^{\downarrow})$ and $\delta({v_{3}}^{\downarrow})$, then
$|\delta({v_{1}}^{\downarrow})|-2=|\delta({v_{1}}^{\downarrow})\cap\delta({v_{2}}^{\downarrow})|+|\delta({v_{1}}^{\downarrow})\cap\delta({v_{3}}^{\downarrow})|$
which contradicts $P_{2}$. Imagine $e$ is in none of
$\delta({v_{2}}^{\downarrow})$ and $\delta({v_{3}}^{\downarrow})$, then
$|\delta({v_{1}}^{\downarrow})|=|\delta({v_{1}}^{\downarrow})\cap\delta({v_{2}}^{\downarrow})|+|\delta({v_{1}}^{\downarrow})\cap\delta({v_{3}}^{\downarrow})|$
which again contradicts $P_{2}$. ∎

Lemma 3.5 and 3.6 characterize an induced cut of size 3 when it shares 2 edges
and 3 edges with a spanning tree respectively. Similar to a min-cut of size 2,
here again we have few different cases. These lemmas unify all the different
cases. We will discuss these different cases in Chapter 5.

We will work with an arbitrary BFS tree $\mathcal{T}$ of the given network.
Whenever a quantity is computed with respect to this BFS tree $\mathcal{T}$,
we will skip the redundant $\mathcal{T}$ from the subscript or superscript,
for example $\pi\left(v\right)$ instead of $\pi_{{\mathcal{T}}}\left(v\right)$
and ${v}^{\downarrow}$ instead of ${v}^{\downarrow{\mathcal{T}}}$. At the
beginning each node $v\neq r$ knows $\ell\left(v\right)$, $\pi\left(v\right)$
and the ancestor set $\mathcal{A}\left(v\right)$. The BFS tree and these
associated quantities can be computed in the beginning in $O(D)$ rounds. For
any node $v$ which is not the root of the BFS tree, $\ell\left(v\right)$ and
$\pi\left(v\right)$ are known to $v$ at the time of construction of the BFS
tree as shown in the proof of the Lemma 2.1. Further the ancestor set
$\mathcal{A}\left(v\right)$ can also be known to node $v$ in $O(D)$ rounds
using _Broadcast Type - 1_. And can be done as follows: each node $a$ tells
all the nodes in the set ${a}^{\downarrow}$ about it being one the ancestor.
This information is just of size $O(\log n)$ bits.

###  3.2 Our Contribution

In this thesis, we present deterministic algorithm to find min-cuts of size
1,2 and 3.

Figure 3.1: Roadmap for finding small min-cuts

For min-cuts of size $1$ and $2$, our algorithm takes $O(D)$ rounds. For min-
cuts of size $3$, our algorithm takes $O(D^{2})$ rounds.

We use our characterization given in Lemma 3.3, Lemma 3.5 and Lemma 3.6.
Further, in subsequent chapters, we will give communication strategies which
will ensure that at least one node in the network knows about the required
information as per these lemmas whenever a min-cut of the kind exists. The
idea is basically to break the problem into smaller parts. Recall from
Observation 3.1 that a min-cut of size 1 shares an edge with any spanning
tree, a min-cut of size 2 may share 1 or 2 edges and finally a min-cut of size
$3$ may share 1,2 or 3 edges with the tree. In each of these cases, we our
communication strategies ensure that at least one of the node will have the
required information as per the aforementioned characterization lemmas. We
give a road-map of this division in Figure 3.1.

Our results of finding min-cuts are split into two chapters. In Chapter 4, we
present a new technique called the _tree restricted semigroup function_. We
will show that this is enough to optimally find the min-cuts of size $1$ and
$2$. In Chapter 5, we will give algorithm to find min-cut of size $3$. We
introduce two techniques: _sketching_ and _layered algorithm_ to do the same.

##  Chapter 4 Tree Restricted Semigroup Function

In this chapter, we will define tree restricted semigroup function and
demonstrate its utility in finding the induced-cuts of size 1 and 2. A tree
restricted semigroup function is defined with respect to a tree $T$ and is
based on a commutative semigroup. Recall that a commutative semigroup is a set
$\mathcal{X}$ together with a commutative and associative binary operation
$\boxplus$ which is a function
$\boxplus:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}$. Tree restricted
semigroup function is inspired by semigroup function defined in [23, Def.
3.4.3].

Let $\mathcal{X}$ be a commutative semigroup with operator $\boxplus$. Let $T$
be any spanning tree. We will formally define $f:V\rightarrow\mathcal{X}$ to
be a tree restricted semigroup function with respect to the tree $T$ in
Definition 4.1. For any node $v$, $f(v)$ will only depend on the vertex set
${v}^{\downarrow{T}}$. Let $a\in V$ be any node, for each
$v\in\mathcal{A}_{T}\left(a\right)$, node $a$ computes the value $X_{a}^{v}$
through a pre-processing step which is the contribution by node $a$ for
calculating $f(v)$.

######  Definition 4.1 (Tree Restricted Semigroup function).

Let $\mathcal{X}$ be a commutative semigroup with the operator $\boxplus$.
Then, the function $f:V\rightarrow\mathcal{X}$ is a tree restricted semigroup
function if
$f(v)=\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{a\in{v}^{\downarrow{T}}}X_{a}^{v}$

Further for any $a\in V$ and $v\in\mathcal{A}_{T}\left(a\right)$, define
$X_{{a}^{\downarrow{T}}}^{v}=\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{a^{\prime}\in{a}^{\downarrow{T}}}X_{a^{\prime}}^{v}$.
Note that $X_{{a}^{\downarrow{T}}}^{v}\in\mathcal{X}$. We will say that
$X_{{a}^{\downarrow{T}}}^{v}$ is the contribution of nodes in the set
${a}^{\downarrow{T}}$ for computing $f(v)$.

######  Observation 4.2.

Let $a$ be an internal node in the tree $T$ and
$v\in\mathcal{A}_{T}\left(a\right)$ then

$X_{{a}^{\downarrow{T}}}^{v}=X_{a}^{v}\boxplus\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{c\in\operatorname{children}_{T}(a)}X_{{c}^{\downarrow{T}}}^{v}\right)$

######  Observation 4.3.

For any internal node $v$

$f(v)=X_{v}^{v}\boxplus\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{c\in\operatorname{children}_{T}(v)}X_{c^{\downarrow}}^{v}\right)$

1

2 Pre-Processing  __

3 For any node $a,\forall v\in\mathcal{A}_{T}\left(a\right)$, node $a$ knows
$X_{a}^{v}$ through a pre-processing

4

1 Phase  _1 : Aggregation phase run on all node $a$, aggregates
$X_{{a}^{\downarrow{T}}}^{v}\ \forall v\in\mathcal{A}\left(a\right)$_

2

3 for  _rounds $t=1$ to $Depth(T)-\ell_{T}\left(a\right)$_ wait

4 $l\leftarrow 0$

5 for  _rounds $t=Depth(T)-\ell_{T}\left(a\right)+1$ to $h\left(T\right)$_ do

6 $v\leftarrow$ ancestor of node $a$ at level $l$

7 if  _$a$ is leaf node_ then $X_{a^{\downarrow T}}^{v}\leftarrow X_{a}^{v}$

8 else

9 for  _$c\in\operatorname{children}_{T}(a)$_ parallely collect $\langle
l,X_{c^{\downarrow T}}^{v}\rangle$

10 $X_{a^{\downarrow T}}^{v}\leftarrow
X_{a}^{v}\boxplus\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{c\in\operatorname{children}_{T}(a)}X_{c^{\downarrow
T}}^{v}\right)$

11

12 send to the parent $\langle l,X_{a^{\downarrow T}}^{v}\rangle$

13 $l\leftarrow l+1$

14

15

1 Phase  _2: Computation Phase (run on all node $v\in V$), finds f(v)_

2 Available Info: __Each node $v$ knows $X_{c^{\downarrow T}}^{v}$ for all
$c\in\operatorname{children}(v)$

3 if  _$v$ is a leaf node_ then $f(v)\leftarrow X_{v}^{v}$

4 else

5 $f(v)\leftarrow
X_{v}^{v}\boxplus\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\boxplus$}}}}}\displaylimits\limits_{c\in\operatorname{children}_{T}(v)}X_{c^{\downarrow
T}}^{v}\right)$

6

Algorithm 1 Tree Restricted Semigroup function

######  Definition 4.4.

A tree restricted semigroup function $f(\cdot)$ is efficiently computable if
for all $v$, $f(v)$ can be computed in $O(Depth(T))$ time in the CONGEST
model.

In Lemma 4.5, we will give sufficient conditions for a tree restricted
semigroup function to be efficiently computable.

######  Lemma 4.5.

For all $a\in V$ and $v\in\mathcal{A}_{T}\left(a\right)$ if
$X_{a}^{v},X_{{a}^{\downarrow{T}}}^{v},f(v)$ are all of size $O(\log n)$ bits
and if $X_{a}^{v}$ can be computed in $O(Depth(T))$ time by node $a$ then the
tree restricted semigroup function $f(\cdot)$ is efficiently computable.

###### Proof.

For any node $v$, tree restricted function $f(v)$ depends on the value
$X_{a}^{v}$ for all $a\in{v}^{\downarrow{T}}$, thus each such node $a$
_convergecasts_ (see Sec. 2.1.2) the required information up the tree which is
supported by aggregation of the values. We will give an algorithmic proof for
this lemma. The algorithm to compute a efficiently computable semigroup
function $f(\cdot)$ is given in Algorithm 1.

The aggregation phase of the algorithm given in Phase 1 runs for at most
$Depth(T)$ time and facilitates a coordinated aggregation of the required
values and convergecasts them in a synchronized fashion. Each node $a$ in
Phase 2, sends $\ell_{T}\left(a\right)$ messages of size $O(\log n)$ to its
parent, each message include $X_{a^{\downarrow T}}^{v}$ where
$v\in\mathcal{A}_{T}\left(a\right)$; which as defined earlier is the
contribution of nodes in $a^{\downarrow T}$ to $f(v)$. This message passing
takes $O(1)$ time since $X_{a^{\downarrow T}}^{v}\in\mathcal{X}$ is of size
$O(\log n)$ bits. For brevity, we assume this takes exactly $1$ round, this
enables us to talk about each round more appropriately as follows: Any node
$a$ at level $\ell_{T}\left(a\right)$ waits for round $t=1$ to
$Depth(T)-\ell_{T}\left(a\right)$. For any $l\in[0,\ell_{T}\left(a\right)-1]$,
in round $t=Depth(T)-\ell_{T}\left(a\right)+l+1$ node $a$ sends to its parent
$\langle l,X_{a^{\downarrow T}}^{v}\rangle$ where $v$ is the ancestor of $a$
at level $l$. When node $a$ is an internal node then as per Observation 4.2,
$X_{{a}^{\downarrow{T}}}^{v}$ depends on $X_{a}^{v}$ which can be pre-
calculated in $O(Depth(T))$ rounds. Also, $X_{a^{\downarrow T}}^{v}$ depends
on $X_{c^{\downarrow T}}^{v}$ for all $c\in\operatorname{children}_{T}(a)$
which are at level $\ell_{T}\left(a\right)+1$ and have send to $a$ (which is
their parent) the message $\langle l,X^{v}_{c^{\downarrow T}}\rangle$ in the
$(Depth(T)-\ell_{T}\left(a\right)+l)^{\text{th}}$ round. For a leaf node $a$,
$X_{a^{\downarrow T}}^{v}=X_{a}^{v}$ which again is covered in pre-processing
step.

In Phase 2, node $v$ computes tree restricted semigroup function $f(v)$. As
per Observation 4.3 of the algorithm each internal node $v$ requires
$X_{{c}^{\downarrow{T}}}^{v}\ \forall c\in\operatorname{children}_{T}(v)$ and
$X_{v}^{v}$. $X_{v}^{v}$ is computed in the pre-processing step. And
$X_{{c}^{\downarrow{T}}}^{v}$ is received by $v$ in the aggregation phase.
When node $v$ is a leaf node, $f(v)$ depends only on $X_{v}^{v}$. ∎

For any node $v$ and a tree $T$, let us define
$\eta_{T}(v)=|\delta({v}^{\downarrow{T}})|$. In Subsection 4.1, we will show
that $\eta_{T}(\cdot)$ is an efficiently computable tree restricted semigroup
function. This will be enough to find if there exists a min-cut of size $1$ or
a min-cut of size $2,3$ which 1-respects our fixed spanning tree.

Further in Subsection 4.2, we will find induced cuts of size 2 and define a
tree restricted semigroup function $\zeta_{T}(\cdot)$ which will enable us to
find induced-cuts of size 2. As mentioned earlier, we will work with a fixed
BFS tree $\mathcal{T}$. We will skip the redundant $\mathcal{T}$ in the
notations. For example $\eta(\cdot)$ instead of $\eta_{T}(\cdot)$ and
$\zeta(\cdot)$ instead of $\zeta_{T}(\cdot)$.

###  4.1 Min-Cuts of size 1

In this subsection we will prove that the function $\eta(\cdot)$ is an
efficiently computable tree restricted semigroup function. Here we will work
with our fixed BFS tree $\mathcal{T}$. Recall that the function
$\eta:V\rightarrow[m]$ where $\eta(v)=|\delta(v^{\downarrow})|$ and
$\delta(v^{\downarrow})$ is the cut induced by the vertex set
$v^{\downarrow}$. For any node $a\in v^{\downarrow}$, we will use
$H_{a}^{v}\triangleq|\delta(a)\cap\delta({v}^{\downarrow})|$. This is equal to
the number of vertices adjacent to $a$ which are not in vertex set
$v^{\downarrow}$. The commutative semigroup associated here is the set of all
positive integers $\mathbb{Z}^{+}$ with ‘addition’operator. Thus for a node
$a\in\mathcal{A}\left(v\right)$,
$H_{{a}^{\downarrow}}^{v}=\sum_{a^{\prime}\in{a}^{\downarrow}}H_{a^{\prime}}^{v}$.
We give the pre-processing steps in Algorithm 2 which calculates $H_{a}^{v}$
for all $v\in\mathcal{A}\left(a\right)$

1 for  _$b$ adjacent to $a$_ parallely send the ancestor set
$\mathcal{A}\left(a\right)$ to $b$

2 for  _$b$ adjacent to $a$_ parallely receive the ancestor set
$\mathcal{A}\left(b\right)$

3 for  _$v\in\mathcal{A}\left(a\right)$_ do

4 $H_{a}^{v}\leftarrow|\left\\{b\mid(a,b)\in E,\
v\notin\mathcal{A}\left(b\right)\right\\}|$

/* node $a$ can execute the above step locally because it knows
$\mathcal{A}\left(b\right)$, $\forall\ (a,b)\in E$ */

5

Algorithm 2 Pre-Processing for computing the function $\eta(\cdot)$ (run at
all node $a$ for finding $H^{v}_{a}\ \forall\ v\in\mathcal{A}\left(a\right)$)

######  Observation 4.6.

Pre processing as given in Algorithm 2 takes $O(D)$ time.

###### Proof.

Any node $a$ has at most $D$ ancestors in $\mathcal{T}$. So for every node $b$
adjacent to $a$, it takes $O(D)$ time to communicate the set
$\mathcal{A}\left(a\right)$ to it. Similarly, it takes $O(D)$ time to receive
the set $\mathcal{A}\left(b\right)$ from node $b$. Now $H_{a}^{v}$ for any
$v\in\mathcal{A}\left(a\right)$ will just be an internal computation at node
$a$. ∎

######  Lemma 4.7.

$\eta(\cdot)$ is an efficiently computable tree restricted semigroup function.

###### Proof.

Let $v\in V$, $\eta(v)$ is the number of edges going out of the vertex set
${v}^{\downarrow}$. That is $\forall a\in{v}^{\downarrow}$, $\eta(v)$ is the
sum of the number of vertices incident to $a$ which are not in the set
${v}^{\downarrow}$. Thus $\eta(v)=\sum_{a\in{v}^{\downarrow}}H_{a}^{v}$. By
Observation 4.6, for all $v\in\mathcal{A}\left(a\right)$, $H_{a}^{v}$ can be
computed in $O(D)$ time. Also for any $v$, $\eta(v)$ could be as big as the
number of edges $m$. Therefore, for any $a\in V$ and
$v\in\mathcal{A}\left(a\right)$ we have, $0\leq H_{a}^{v}\leq
H_{{a}^{\downarrow}}^{v}\leq\eta(v)\leq m$. Thus
$H_{a}^{v}$,$H_{{a}^{\downarrow}}^{v}$ and $f(v)$ can be represented in
$O(\log n)$ bits. Hence by Lemma 4.5, $\eta(\cdot)$ is an efficiently
computable tree restricted semigroup function. ∎

To compute $\eta(\cdot)$, we use Algorithm 1 given in Lemma 4.5. Further
during the computation of $\eta(\cdot)$, each node $a$ computes
$H_{{a}^{\downarrow}}^{v}$ for all $v\in\mathcal{A}\left(a\right)$ which is
the aggregated value of all the decendents of node $a$. We summarize these
results in the following Lemmas.

######  Lemma 4.8.

The function $\eta(\cdot)$ can be computed in $O(D)$ time for every node $v\in
V$.

###### Proof.

In Lemma 4.7, we show that $\eta(\cdot)$ is an efficiently computable tree
restricted semigroup function defined with respect to the BFS tree
$\mathcal{T}$. Also, $Depth(\mathcal{T})=O(D)$. Thus by Definition 4.1,
$\eta(\cdot)$ can be computed in $O(D)$ ∎

######  Lemma 4.9.

For each node $a$ and $v\in\mathcal{A}\left(a\right)$, node a knows
$H_{{a}^{\downarrow}}^{v}=|\delta\left({a}^{\downarrow}\right)\cap\delta\left({v}^{\downarrow}\right)|$
in $O(D)$ rounds.

###### Proof.

During the computation of the tree restricted semigroup function
$\eta(\cdot)$, each node $a$ for every $v\in\mathcal{A}\left(a\right)$,
computes the aggregated value
$H_{{a}^{\downarrow}}^{v}=\sum_{a^{\prime}\in{a}^{\downarrow}}H_{a}^{v}$ which
is the contribution of nodes in ${a}^{\downarrow}$ towards the computation of
$\eta(v)$. Thus the lemma follows. ∎

######  Theorem 4.10.

Min-cut of size one (bridge edges) can be found in $O(D)$ time.

###### Proof.

For any node $v\neq r$, the edge
$(\pi\left(v\right),v)\in\delta(v^{\downarrow})$. Thus when $\eta(v)=1$, then
$(\pi\left(v\right),v)$ is the only edge in $\delta(v^{\downarrow})$ and is a
cut edge. ∎

######  Lemma 4.11.

If $\eta(v)=k$ then $\delta(v^{\downarrow})$ is a cut-set of size $k$.

Having found $\eta(\cdot)$ for all the nodes we downcast them. That is each
node $v$, downcasts its $\eta(v)$ value to the vertex set ${v}^{\downarrow}$.
This kind of broadcast is similar to _Broadcast Type -1_ defined in Chapter 2.
Thus by Lemma 2.4, this can be done in $O(D)$ time. That is all nodes
$a\in{v}^{\downarrow}$ will have the value of $\eta(v)$ in $O(D)$ time. This
will be useful for the algorithm to find induced cuts of size 2 given in next
subsection. We quantify the same in the following lemma.

######  Lemma 4.12.

For any node $v$, the nodes in the vertex set ${v}^{\downarrow}$ know
$\eta(v)$ in $O(D)$ rounds.

###  4.2 Min-Cuts of size 2

In this subsection, we will give an algorithm to find min-cuts of size 2. The
theme here will be the use of tree restricted semigroup function. We will
define a new tree restricted semigroup function $\zeta(\cdot)$ which will be
based on a specially designed semigroup.

Before we get into details of $\zeta(\cdot)$, we will give details about cuts
of size $2$. Let $A\subset V$ and $|\delta(A)|=2$. The question here is to
find $\delta(A)$. Here, $\delta(A)$ could share either one edge with the tree
$T$, or it could share $2$ edges with the tree. When $\delta(A)$ shares one
edge with the tree then it can be found in $O(D)$ rounds as described by Lemma
4.11. We make the following observation for the case when $\delta(A)$,
2-respects the tree. In this case,
$\delta(A)=\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$ for
some $a,w\in V\setminus r$ and $a\neq w$.

######  Observation 4.13.

Let $A\subset V$ and $|\delta(A)|=2$. Also, let $\delta(A)$ 2-respect the tree
$\mathcal{T}$ then
$\delta(A)=\delta({a}^{\downarrow})\oplus\delta({w}^{\downarrow})$ for some
$a\neq w$ and $a,w\in V\setminus r$. Further either
${{a}^{\downarrow}}\subset{{w}^{\downarrow}}$ (nested) or
${{a}^{\downarrow}}\cap{{w}^{\downarrow}}=\emptyset$ (mutually disjoint).

###### Proof.

Let $\delta(A)=\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$
such that $a\neq w$ and $a,w\in V\setminus r$. WLOG let
$\ell\left(a\right)\geq\ell\left(w\right)$. Because of the tree structure,
either ${a}^{\downarrow}\subset{w}^{\downarrow}$ or
${a}^{\downarrow}\cap{w}^{\downarrow}=\emptyset$. When
${a}^{\downarrow}\subset{w}^{\downarrow}$ then the induced cut $\delta(A)$ is
the cut set
$({w}^{\downarrow}\setminus{a}^{\downarrow},V\setminus({w}^{\downarrow}\setminus{a}^{\downarrow}))=\delta({w}^{\downarrow}\setminus{a}^{\downarrow})$.
Since ${a}^{\downarrow}\subset{w}^{\downarrow}$ thus
${w}^{\downarrow}\setminus{a}^{\downarrow}={w}^{\downarrow}\oplus{a}^{\downarrow}$.
Hence
$\delta({w}^{\downarrow}\setminus{a}^{\downarrow})=\delta({w}^{\downarrow}\oplus{a}^{\downarrow})$
and finally by Corollary 2.7, we have
$\delta({a}^{\downarrow}\oplus{w}^{\downarrow})=\delta({a}^{\downarrow})\oplus\delta({w}^{\downarrow})$.
Similarly, when ${a}^{\downarrow}\cap{w}^{\downarrow}=\emptyset$ then the
induced cut $\delta(A)$ is the cut set
$({a}^{\downarrow}\cup{w}^{\downarrow},V\setminus{a}^{\downarrow}\cup{w}^{\downarrow})=\delta({a}^{\downarrow}\cup{w}^{\downarrow})=\delta({a}^{\downarrow}\oplus{w}^{\downarrow})=\delta({a}^{\downarrow})\oplus\delta({w}^{\downarrow})$.
∎

The above observation states that we have two different cases when an induced-
cut of size $2$ shares both the edges with the tree. For any $A,B\subseteq V$,
let $\gamma(A,B)=|\delta(A)\cap\delta(B)|$. In this subsection, we will prove
the following lemma. This lemma will be enough to prove that the min-cuts of
size $2$ can be deterministically found in $O(D)$ rounds. Moreover, it will
also help us find min-cuts of size 3 as given in Chapter 5.

######  Lemma 4.14.

Let $a,w$ be two nodes. WLOG let $\ell\left(a\right)\geq\ell\left(w\right)$.
If $\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$ is a cut set
induced by ${a}^{\downarrow}\oplus{w}^{\downarrow}$ and if
$\gamma({a}^{\downarrow},{w}^{\downarrow})>0$ then such an induced cut can be
found in $O(D)$ rounds by node $a$.

Using the above lemma we now prove the following theorem.

######  Theorem 4.15.

Min-cuts of size $2$ can be found in $O(D)$ rounds.

###### Proof.

When there is a min-cut of size 2, it either 1-respects the tree or 2-respects
the tree. When it 1-respects the tree, by Lemma 4.11, we know that it can be
found in $O(D)$ rounds because this only requires computation of
$\eta(\cdot)$.

When a min-cut of size 2, 2-respects the tree then by Lemma 4.13 we know that
the cut is of the form
$\delta({w}^{\downarrow})\oplus\delta({a}^{\downarrow})$ for some nodes $a$
and $w$. Moreover $\gamma({a}^{\downarrow},{w}^{\downarrow})>0$ since there is
not cut of size $1$. From Lemma 4.14 we know that this can be found in $O(D)$
rounds. ∎

We will now prove Lemma 4.14. When the induced cut of size 2, 2-respects the
tree, we know by Observation 4.13 that there could be two different cases. For
the easy case when ${{a}^{\downarrow}}\subset{{w}^{\downarrow}}$, we know from
Lemma 4.9 that
$H_{{a}^{\downarrow}}^{w}=|\delta({a}^{\downarrow})\cap\delta({w}^{\downarrow})|=\gamma({{a}^{\downarrow}},{{w}^{\downarrow}})$
is known by node $a$ in $O(D)$ rounds. Also from Lemma 4.12, $\eta(w)$ is
known by all the vertices $a\in{{w}^{\downarrow}}$. Hence, if
$\left\\{(\pi\left(w\right),w),(\pi\left(a\right),a)\right\\}$ is an induced
cut and $a\in{w}^{\downarrow}$ and $a\neq w$, then as per Lemma 3.3 node $a$
has the required information to find the induced cut. The following lemma
summarizes this.

######  Lemma 4.16.

Let $a,w$ be two vertices such that ${a}^{\downarrow}\subset{w}^{\downarrow}$.
Let
$\delta({a}^{\downarrow}\oplus{w}^{\downarrow})=\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$
be an induced cut, then node $a$ can find such a cut in $O(D)$ rounds.

The other case is when ${a}^{\downarrow}$ and ${w}^{\downarrow}$ are disjoint
sets. This is the non-trivial part for finding an induced cut of size 2.
Recall from Lemma 3.3, that to make a decision about an induced cut of the
form $\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$ we require
one of the node in the network to know
$\gamma({a}^{\downarrow},{w}^{\downarrow}),\eta(a)$ and $\eta(w)$. The idea
here is for node $a$ (when $\ell\left(a\right)\geq\ell\left(w\right)$) to find
$\eta(w)$ and $\gamma({a}^{\downarrow},{w}^{\downarrow})$ which is quite a
challenge because there does not exists a straightforward way through
broadcast or convergecast. Moreover, there may not even exist an edge between
the vertices $a$ and $w$. To deal with this, we introduce a new tree
restricted semigroup function $\zeta(\cdot)$

The tree restricted semigroup function $\zeta(\cdot)$ is based on a specially
defined semigroup $\mathcal{Z}$. Before we give further details and intuition
about the function $\zeta(\cdot)$, let us define the semigroup $\mathcal{Z}$.
There are two special elements $\mathbb{e}$ and $\nparallel$ in the semigroup
$\mathcal{Z}$. Apart from these special elements all other $Z\in\mathcal{Z}$
are a four tuple. Let the four-tuple be given as $Z=\langle
Z[1],Z[2],Z[3],Z[4]\rangle$, here $Z[1],Z[2]\in V$ and
$Z[3],Z[4]\in\mathbb{Z}^{+}$.

The operator associated with the semigroup $\mathcal{Z}$ is $\odot$. Special
elements $\mathbb{e}$ and $\nparallel$ are the identity and the absorbing
element with respect to the operator $\odot$ of the semigroup $\mathcal{Z}$.
These special elements are defined in such a way that for any
$Z\in\mathcal{Z}$, $Z\odot\mathbb{e}=Z=\mathbb{e}\odot Z$ and $Z\
\odot\nparallel\ =\ \nparallel\ =\ \nparallel\odot Z$. (Here the symbols
$\mathbb{0},\mathbb{1}$ are not chosen as identity and absorbing elements,
because $\mathbb{e}$ corresponds to zero edges and $\nparallel$ is considered
as a zero of the semigroup which we will see in Property 4.18). In Algorithm
3, we define the operator $\odot$.

// for $i\in\left\\{1,2,3,4\right\\}$ let $Z_{1}[i]$ be the $i^{\text{th}}$
element in 4-tuple of $Z_{1}$. Similarly for $Z_{2}$

1 if  _one of $Z_{1},Z_{2}$ is $\nparallel$_ then return $\nparallel$

2 else if  _$Z_{1}=\mathbb{e}$_ then return $Z_{2}$

3 else if  _$Z_{2}=\mathbb{e}$_ then return $Z_{1}$

4 else if  _$Z_{1}[1:3]=Z_{2}[1:3]$_ then return $\langle
Z_{1}[1],Z_{1}[2],Z_{1}[3],Z_{1}[4]+Z_{2}[4]\rangle$

5 else return $\nparallel$

Algorithm 3 $Z_{1}\odot Z_{2}$ (Both $Z_{1},Z_{2}\in\mathcal{Z}$)

######  Observation 4.17.

$\odot\ (\texttt{zeta-operator})$ is commutative and associative.

###### Proof.

Commutativity of $\odot$ is straightforward and is implied by the
commutativity of addition over $\mathbb{Z}^{+}$. For associativity, let’s
imagine there exist $Z_{1},Z_{2},Z_{3}\in\mathcal{Z}$. Further let’s imagine
that $Z_{1},Z_{2},Z_{3}\notin\left\\{\nparallel,\mathbb{e}\right\\}$. Now when
the first two elements of each of the four tuples $Z_{1},Z_{2},Z_{3}$ is same,
then associativity is trivial and implied by the associativity of the addition
operator over $\mathcal{Z}^{+}$. When the first two elements are not equal in
$Z_{1},Z_{2},Z_{3}$ then $Z_{1}\odot(Z_{2}\odot Z_{3})=(Z_{1}\odot Z_{2})\odot
Z_{3}=\ \nparallel$. Similarly, If one of $Z_{1},Z_{2},Z_{3}$ is $\nparallel$,
then also $Z_{1}\odot(Z_{2}\odot Z_{3})=(Z_{1}\odot Z_{2})\odot Z_{3}=\
\nparallel$, hence associativity is implied. And lastly when one of
$Z_{1},Z_{2},Z_{3}$ is $\mathbb{e}$, then $Z_{1}\odot(Z_{2}\odot Z_{3})$
becomes an operation between just two elements and associativity is implied
directly. ∎

For any node $v$, define the edge set
$E\left\\{\zeta(v)\right\\}\triangleq\delta({v}^{\downarrow})\setminus(\pi(v),v)$.
The value of $\zeta(v)$ depends on the edge set $E\left\\{\zeta(v)\right\\}$.
For any node $a$ and $v\in\mathcal{A}\left(a\right)$, let
$E\left\\{Z_{a}^{v}\right\\}\triangleq
E\left\\{\zeta(v)\right\\}\cap\delta(a)$. We define $Z_{a}^{v}$ as per the
Property 4.18.

######  Property 4.18.

For any node $a$ and $v\in\mathcal{A}\left(a\right)$, $Z_{a}^{v}$ takes one of
the following three values:-

  1. i.

$\mathbb{e}$ when $E\left\\{Z_{a}^{v}\right\\}=\emptyset$

  2. ii.

${\langle w,\pi\left(w\right),\eta(w),\gamma(a,{{w}^{\downarrow}})\rangle}$
when there exists a node $w$ at level $\ell\left(v\right)$ such that all the
edges in $E\left\\{Z_{a}^{v}\right\\}$ have one endpoint in
${{w}^{\downarrow}}$

  3. iii.

$\nparallel$ otherwise

Similar to the previous subsection the semigroup function $\zeta(\cdot)$ is
defined as $\zeta(v)\triangleq\bigodot_{a\in{v}^{\downarrow}}Z_{a}^{v}$. We
will say that $Z_{{{a}^{\downarrow}}}^{v}$ is the contribution of nodes in
vertex set ${a}^{\downarrow}$ to compute $\zeta(v)$. We will now prove that
for all node $a\in V$ and $v\in\mathcal{A}\left(a\right)$, $Z_{a}^{v}$ can be
computed in $O(D)$ time in Lemma 4.19, then using Definition 4.1 and Lemma
4.5, we will prove that $\zeta(\cdot)$ is an efficiently computable tree
restricted semigroup function.

For any $l<\ell\left(a\right)$, let $\alpha(a,l)$ be the ancestor of node $a$
at level $l$. For notational convenience let $\alpha(a,\ell\left(a\right))=a$.

######  Lemma 4.19.

For all node $a\in V$ and $v\in\mathcal{A}\left(a\right)$, $Z_{a}^{v}$ can be
computed in $O(D)$ time as defined in Property 4.18.

###### Proof.

Here we will give an algorithmic proof, We describe the steps in Algorithm 4.
Further we will prove that this algorithm correctly finds $Z_{a}^{v}$ and
takes $O(D)$ time.

1 $\mathcal{N}(a)\leftarrow\left\\{b\mid(a,b)\in E,(a,b)\ \text{is a non-tree
edge}\right\\}$

2 for  _all $b\in\mathcal{N}(a)$_ parallely send tuples
$\langle\ell\left(u\right),\eta(u),u\rangle$ for all
$u\in\mathcal{A}\left(a\right)$ to $b$

3 for  _all $b\in\mathcal{N}(a)$_ parallely receive tuples
$\langle\ell\left(u\right),\eta(u),u\rangle$ for all
$u\in\mathcal{A}\left(b\right)$

4 $l_{\min}\leftarrow\min(\left\\{\ell\left(b\right)\ |\
b\in\mathcal{N}(a)\right\\}\cup\ell(a))$

5 if  _$l_{\min}\neq\ell(a)$_ then

6 for  _$v\in\left\\{\alpha(a,l)\mid l\in(l_{\min},\ell(a)]\right\\}$_ do
$Z_{a}^{v}=\ \nparallel$

7

8for  _$l=l_{\min}$ to $1$_ do

9 $v\leftarrow\alpha(a,l)$

// $A^{l}$ is set of ancestors at level $l$ of nodes in $\mathcal{N}(a)$
except $v$

10 $A^{l}\leftarrow\left\\{\alpha(b,l)\mid
b\in\mathcal{N}(a)\right\\}\setminus v$

11 if  _$A^{l}=\emptyset$_ then $Z^{v}_{a}\leftarrow\mathbb{e}$

12 else if  _$|A^{l}|=1$_ then

13 $w\leftarrow$ element in singleton $A^{l}$

14 $\gamma({{w}^{\downarrow}},a)\leftarrow|\left\\{b\mid
b\in\mathcal{N}(a),\alpha(b,l)=w\right\\}|$

15 $Z^{v}_{a}\leftarrow\langle
w,\pi\left(w\right),\eta(w),\gamma({{w}^{\downarrow}},a)\rangle$

16 else $Z^{v}_{a}\leftarrow\nparallel$

17

Algorithm 4 Pre-Processing step for $\zeta$ (run at all node $a$ for finding
$Z_{a}^{v}$ for all $v\in\mathcal{A}\left(a\right)$)

As per Property 4.18, $Z_{a}^{v}$ just depend on the nodes adjacent to the
node $a$. The required information is received and sent from the adjacent
nodes in Algorithm 4 at line 4 and 4. Each of these takes only $O(D)$ time
because at max $O(D)$ messages of $O(\log n)$ bits are communicated.
$\mathcal{N}(a)$ is the non-tree neighbors of node $a$ found in line 4. In
Algorithm 4, decision in regard to $Z_{a}^{v}$ is taken based on $A^{\ell(v)}$
which is the set of ancestors at level $\ell\left(v\right)$ of nodes in
$\mathcal{N}(a)$ except the node $v$.

When $A^{\ell(v)}=\emptyset$, then in line 4, $Z_{a}^{v}$ is set to
$\mathbb{e}$. For bullet (i) of Property 4.18, we need to prove that
$E\left\\{Z_{a}^{v}\right\\}=\emptyset\implies A^{\ell(v)}=\emptyset$. Here
$E\left\\{Z_{a}^{v}\right\\}=\delta({v}^{\downarrow})\setminus(\pi\left(v\right),v)\cup\delta(a)$.
When $a\neq v$, then $E\left\\{Z_{a}^{v}\right\\}$ is the set of all the edges
which are incident on $a$ and goes out of the vertex set ${v}^{\downarrow}$.
Now when $E\left\\{Z_{a}^{v}\right\\}=\emptyset$, then all edges incident on
$a$ have the other endpoint in the vertex set ${v}^{\downarrow}$. Thus
$A^{\ell(v)}=\emptyset$. When $a=v$, here $E\left\\{Z_{v}^{v}\right\\}$ is the
set of all edges other then $(\pi\left(v\right),v)$ which are incident on $v$
and goes out of the vertex set ${v}^{\downarrow}$. Note that
$(\pi\left(v\right),v)$ is a tree-edge thus
$\pi\left(v\right)\notin\mathcal{N}(a)$. Thus
$E\left\\{Z_{v}^{v}\right\\}=\emptyset\implies A^{\ell(v)}=\emptyset$.

Now for correctness, if $E\left\\{Z_{a}^{v}\right\\}=\emptyset$ and $v\neq a$
then no edge incident on node $a$ goes out of ${v}^{\downarrow}$, hence the
set $A^{\ell(v)}=\emptyset$. When $v=a$, we know that $\mathcal{N}(v)$ (in
line 4) contains only non-tree neighbors, thus
$\pi\left(v\right)\notin\mathcal{N}(v)$. We know that edge
$(\pi\left(v\right),v)\notin E\left\\{Z_{v}^{v}\right\\}$. Thus here when
$E\left\\{Z_{v}^{v}\right\\}=\emptyset$ then no edge other than
$(\pi\left(v\right),v)$ incident on $v$ goes out of ${v}^{\downarrow}$, thus
$A^{\ell(v)}=\emptyset$. Hence in both the cases $Z_{a}^{v}$ is correctly set
to $\mathbb{e}$. (in line 4)

For the other two bullet’s in Property 4.18, we employ the same idea. If
$A^{\ell\left(v\right)}=\left\\{w\right\\}$ (for some node $w$) then it
implies that all the neighbours adjacent to node $a$ have a common ancestor
$w$ other than $v$ and thus $Z_{a}^{v}$ captures the required information
about node $w$. And when $|A^{\ell\left(v\right)}|>1$ it simply means there
are more than one node at level $\ell\left(v\right)$ as given in bullet
$(iii)$ of Property 4.18. ∎

Similar to previous section,
$Z_{{a}^{\downarrow}}^{{v}}\triangleq\bigodot_{a^{\prime}\in{a}^{\downarrow}}Z_{a^{\prime}}^{v}$.
Since for any $a^{\prime}\in{a}^{\downarrow}$, $Z_{{{a^{\prime}}}}^{v}$
depends on $E\left\\{\zeta(v)\right\\}\cap\delta({a^{\prime}})$ thus
$Z_{{{a}^{\downarrow}}}^{v}$ depends on
$E\left\\{Z_{{{a}^{\downarrow}}}^{v}\right\\}=\bigcup_{a^{\prime}\in{a}^{\downarrow}}E\left\\{Z_{{{a^{\prime}}}}^{v}\right\\}=E\left\\{\zeta(v)\right\\}\cap\delta({a}^{\downarrow})$.
The following lemma about $Z_{{a}^{\downarrow}}^{v}$ is now implicit and
immediately follows from Property 4.18.

######  Lemma 4.20.

For any node $a$ and $v\in\mathcal{A}\left(a\right)$,
$Z_{{a}^{\downarrow}}^{v}$ depends on the edge set
$E\left\\{Z_{{a}^{\downarrow}}^{v}\right\\}=\bigcup\limits_{a^{\prime}\in{a}^{\downarrow}}E\left\\{Z_{a^{\prime}}^{v}\right\\}$
and takes one of the following values

  1. a)

$\mathbb{e}$ when $E\left\\{Z_{{a}^{\downarrow}}^{v}\right\\}=\emptyset$

  2. b)

${\langle
w,\pi\left(w\right),\eta(w),\gamma({a}^{\downarrow},{{w}^{\downarrow}})\rangle}$
when there exists a node $w$ at level $\ell\left(v\right)$ such that all the
edges in $E\left\\{Z_{{a}^{\downarrow}}^{v}\right\\}$ have one endpoint in
${{w}^{\downarrow}}$

  3. c)

$\nparallel$ otherwise

Basically, $Z_{{a}^{\downarrow}}^{v}$ captures if there exists some node $w$
at level $\ell\left(v\right)$ such that all the edges which are in
$\delta({a}^{\downarrow})$ and go out of the vertex set ${v}^{\downarrow}$,
have the other end point in the vertex set ${w}^{\downarrow}$.

######  Lemma 4.21.

$\zeta(\cdot)$ is an efficiently computable semigroup function.

###### Proof.

In Lemma 4.19, it was shown that there exists a $O(D)$ time algorithm to
compute $Z_{a}^{v}$ for any node $a$ and $v\in\mathcal{A}\left(a\right)$.
Further each such $Z_{a}^{v}$ is either a special symbol among
$\mathbb{e},\nparallel$ or a four tuple. It is easy to see that this four
tuple is of $O(\log n)$ bits because the first two elements in the four tuple
are node ids and the last two are integers which cannot exceed the number of
edges and we require $O(\log n)$ bits to represent them. Now invoking Lemma
4.5, we know that $\zeta(\cdot)$ is an efficiently computable tree restricted
semigroup function. ∎

######  Lemma 4.22.

For all nodes $a$ and $v\in\mathcal{A}\left(a\right)$,
$Z_{{a}^{\downarrow}}^{v}$ can be computed in $O(D)$ time.

###### Proof.

Since $\zeta(\cdot)$ is an efficiently computable semigroup function and can
be computed in $O(D)$ rounds. Also, during the computation of $\zeta(\cdot)$,
for all node $a$ and $v\in\mathcal{A}\left(a\right)$,
$Z_{{a}^{\downarrow}}^{v}$ is also computed. ∎

######  Lemma 4.23.

Let $a,w$ be two vertices such that
${w}^{\downarrow}\cap{a}^{\downarrow}=\emptyset$. WLOG, let
$\ell\left(a\right)\geq\ell\left(w\right)$. Let
$\left\\{(\pi\left(a\right),a),(\pi\left(w\right),w)\right\\}$ be an induced
cut such that $\gamma({w}^{\downarrow},{a}^{\downarrow})>0$, then node $a$ can
find it in $O(D)$ rounds.

###### Proof.

Here we have to prove that node $a$ will have access to $\eta(w)$ and
$\gamma({w}^{\downarrow},{a}^{\downarrow})$ if such a min cut occurs. Then
confirming the min-cut is easy by Lemma 3.3. Let $v$ be the ancestor of node
$a$ at level $\ell\left(w\right)$. By Observation 4.20, we know that
$Z_{{a}^{\downarrow}}^{v}=\langle
w,\pi\left(w\right),\eta(w),\gamma({w}^{\downarrow},{a}^{\downarrow})\rangle$
in this case. Thus, the required information will be available at node $a$. ∎

###### Proof of Lemma 4.14.

When the induced cut 2-respects the tree that is it is a symmetric difference
of two tree cuts $\delta({{a}^{\downarrow}})$ and $\delta({{w}^{\downarrow}})$
for some $a,w\in V\setminus r$. As per Observation 4.13 here two cases could
occur. The nested case when ${{a}^{\downarrow}}\subset{{w}^{\downarrow}}$ and
the mutually disjoint case when ${{a}^{\downarrow}}\cap{{w}^{\downarrow}}$,
results regarding them are given in Lemma 4.16 and Lemma 4.23. In line 5 and 5
of Algorithm 5, we give details about the actual search.

1 Available Info: __Each node $a$, $\forall v\in\mathcal{A}\left(a\right)$
knows $\eta(v),H_{{a}^{\downarrow}}^{v}$ and $Z_{{a}^{\downarrow}}^{v}$ (Lemma
4.12,4.9,4.22)

1 for  _$l=1$ to $\ell(a)$_ do

$v\leftarrow$ $\alpha(a,l)$ // ancestor of node $a$ at level $l$

2 if
_$Z_{{{a}^{\downarrow}}}^{v}\notin\left\\{\mathbb{e},\nparallel\right\\}$_
then

3 Let $Z_{{{a}^{\downarrow}}}^{v}=\langle
w,\pi\left(w\right),\eta(w),\gamma({{w}^{\downarrow}},{{a}^{\downarrow}})\rangle$

4 if  _$\eta(a)-\gamma({{w}^{\downarrow}},{{a}^{\downarrow}})=1$ &
$\eta(w)-\gamma({{w}^{\downarrow}},{{a}^{\downarrow}})=1$_ then

5 $\left\\{(\pi\left(w\right),w),(\pi\left(a\right),a)\right\\}$ is a 2-cut

6

7 if  _$v\neq a$ & $\eta(v)-H_{{{a}^{\downarrow}}}^{v}=1$ &
$\eta(a)-H_{{{a}^{\downarrow}}}^{v}=1$_ then

8 $\left\\{(\pi\left(v\right),v),(\pi\left(a\right),a)\right\\}$ is a 2-cut

9

Algorithm 5 Algorithm to find 2-cut for node $a$

∎

In this chapter, we formally defined tree restricted semigroup function.
Further, we introduced two different types of tree restricted semigroup
function $\eta(\cdot)$ and $\zeta(\cdot)$. We showed that these are enough to
find min-cuts of size 1 and 2. In the next chapter, we will give algorithms to
find min-cuts of size $3$.

##  Chapter 5 Min-Cuts of size three

In this chapter, we will give an algorithm to find a min-cut of size three.
The idea here is to use Lemma 3.5 and Lemma 3.6 given in Chapter 3 which
characterizes the min-cut of size $3$. Having laid down these characterization
lemmas, the critical aspect which remains to find the min-cut of size 3 (if it
exists) is to communicate the required quantities by the characterizing lemmas
to at least one node in the network whenever a min-cut of the kind occurs. For
this chapter, we will assume that a min-cut of size $1,2$ do not occur.

Recall that we have fixed a BFS tree $\mathcal{T}$ in the beginning. If there
exists a min-cut in the network, there could be 7 different cases. These cases
are different to each other based on the relation of the min-cut to the fixed
BFS tree $\mathcal{T}$. We enumerate these cases in Lemma 5.1. Further, give
an algorithmic outline about how these cases can be found in Table 5.1.

######  Lemma 5.1.

If there exists a min-cut of size 3 then the following cases may arise for
some $v_{1},v_{2},v_{3}\in V\setminus r$ and $e,f$ as non-tree edge.

  1. CASE-1

$\left\\{(\pi\left(v_{1}\right),v_{1}),e,f\right\\}$ is a min-cut

  2. CASE-2

$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a min-cut such that ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$

  3. CASE-3

$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a min-cut such that
${v_{2}}^{\downarrow}\cap{v_{1}}^{\downarrow}=\emptyset$

  4. CASE-4

$\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 and
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$

  5. CASE-5

$\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 ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{3}}^{\downarrow}\subset{v_{1}}^{\downarrow}$ and
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$

  6. CASE-6

$\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 and ${v_{3}}^{\downarrow},{v_{2}}^{\downarrow}$ and
${v_{1}}^{\downarrow}$ are pairwise mutually disjoint

  7. CASE-7

$\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 and ${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}$,
${v_{1}}^{\downarrow}\cap{v_{2}}^{\downarrow}=\emptyset$ and
${v_{1}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$

###### Proof.

From Observation 3.1, we know that that if there exists a min-cut of size $3$
then it shares either $1,2$ or $3$ edges with the tree $\mathcal{T}$. When a
min-cut of size $3$ shares one edge with the tree then CASE-1 applies. Here
two edges are non-tree edges.

When a min-cut of size $3$ shares 2-edges with the tree $\mathcal{T}$ then
there exists two tree edges. For some node $v_{1},v_{2}\in V\setminus r$ let
these edges be $(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2})$.
WLOG let $\ell\left(v_{1}\right)\leq\ell\left(v_{2}\right)$. Similar to
Observation 4.13, there could be two cases here either $v_{2}\subset v_{1}$ or
$v_{1}\cap v_{2}=\emptyset$. Both of which are described in CASE-2 and CASE-3
respectively.

The non-trivial part here is when the min-cut of size 3 shares all 3 edges
with the tree. Here we will have 4 different cases. Let these cut edges be
$(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2})$ and
$(\pi\left(v_{3}\right),v_{3})$. Also in the beginning let
$\ell\left(v_{1}\right)<\ell\left(v_{2}\right)<\ell\left(v_{3}\right)$. We
start with the case when
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$
which is described in CASE-4. Now when
${v_{3}}^{\downarrow}\not\subset{v_{2}}^{\downarrow}$ then since $v_{2},v_{3}$
are different thus we have
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$ which is CASE-5.
Notice that in both CASE-4 and CASE-5 we have
$({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})\subset{v_{1}}^{\downarrow}$.
Now we move to the different scenario where
$({v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow})\not\subset{v_{2}}^{\downarrow}$.
Here also we may have two cases when
${v_{2}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$ then we get CASE-6
and when ${v_{2}}^{\downarrow}\subset{v_{3}}^{\downarrow}$ then we get CASE-7.
Note that for CASE-6 and CASE-7 we may not require
$\ell\left(v_{1}\right)\leq\ell\left(v_{2}\right)$ and
$\ell\left(v_{1}\right)\leq\ell\left(v_{3}\right)$ ∎

| Characterization | Case | Technique
---|---|---|---
1-respects $\mathcal{T}$ |  - | CASE-1 |  check if for some $v$, $\eta(v)=3$
2-respects $\mathcal{T}$ |  Lemma 3.5 | CASE-2 |  _Broadcast Type - 1_ Section 2.1.2
CASE-3 |  2-Sketch Section 5.1
3-respects $\mathcal{T}$ |  Lemma 3.6 | CASE-4 |  _Broadcast Type - 2_ Section 2.1.2
CASE-5 |  Layered Algorithm Section 5.2
CASE-6 |  3-Sketch Section 5.1
CASE-7 |  Reduced 2-Sketch Section 5.1
Table 5.1: Overview of the case-structure of min-cut of size $3$. A min-cut of
size $3$ if exists may share $1,2$ or $3$ edges with the fixed BFS tree
$\mathcal{T}$.

The different cases as mentioned in Lemma 5.1 are pictorially shown in Figure
5.1.

(a) CASE-2 (Either of $\alpha$ or $\beta$ is 1 and the other is $0$)

(b) CASE-3 (Either of $\alpha$ or $\beta$ is 1 and the other is $0$)

(c) CASE-4 (Both $\alpha$ and $\beta$ are non-zero)

(d) CASE-5 (At least two of $\alpha$, $\beta$ and
$\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$ are non-zero)

(e) CASE-6 (at least two of
$\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow})$,
$\gamma({v_{3}}^{\downarrow},{v_{2}}^{\downarrow})$,
$\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow})$ are non-zero)

(f) CASE-7 (Both $\alpha$ and $\beta$ are non-zero)

Figure 5.1: Different cases of an min cut of size three. Each figure in the
above examples is a snippet of the tree and shows a different case of min-cut
of size 3. Red edges are cut edges. Each shaded region in the above figures
correspond to a vertex set. Sets with same color in the shaded region
correspond to one side of cut. Thick edges with arrow ends may correspond to
zero or more edges between two vertex set. The label on these edges represent
the actual number of edges.

Among these cases, CASE-1 is simple. Here for some node $v_{1}$ the induced
cut is $(V\setminus{v_{1}}^{\downarrow},{v_{1}}^{\downarrow})$. Here we just
need to find the size of tree cut $\eta(v_{1})$ and if there exists such a min
cut of size $3$, then $\eta(v_{1})=3$. This takes $O(D)$ time as shown in
Lemma 4.11.

Among the other cases only CASE-2 and CASE-4 have a simple broadcast based
algorithm which is enough to let at least one of the node know the required
quantities as per Lemma 3.5 and Lemma 3.6. We give the details in the
following lemmas.

######  Lemma 5.2.

When there exists a min-cut of size 3 as given in CASE-2 (for some nodes
$v_{1},v_{2}\in V\setminus r$ and a non-tree edge $e$
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a min-cut such that ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$),
then the cut edges can be found in $O(D)$ time.

###### Proof.

From Chapter 4, we know that each node $v$ knows
$\eta(v)=|\delta({v}^{\downarrow})|$. Also for each
$u\in\mathcal{A}\left(v\right)$, $v$ knows $\eta(u)$ and
$H^{u}_{{v}^{\downarrow}}$ by Lemma 4.12 and 4.9. Thus if there exists an
induced cut as in $\textbf{CASE}-2$ then we just need to make a simple
evaluation based on Lemma 3.5. We give the details of the evaluation in
Algorithm 6.

1 Available Info: __Each node $x$, $\forall v\in\mathcal{A}\left(x\right)$
knows $\eta(v),H_{{x}^{\downarrow}}^{v}$ (Lemma 4.12 ,4.9)

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

2 if  _$\eta(v)-1=H_{{x}^{\downarrow}}^{v}=\eta(x)-2$ OR
$\eta(v)-2=H_{{x}^{\downarrow}}^{v}=\eta(x)-1$_ then

3 $\delta({v}^{\downarrow}\oplus{x}^{\downarrow})$ is an induced cut of size 3

4

5

Algorithm 6 Algorithm to find an induced cut of size $3$ as given in CASE-2
(for some nodes $v_{1},v_{2}\in V\setminus r$ and a non-tree edge $e$
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a min-cut such that ${v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$) run
on all node $x\in V\setminus r$

∎

######  Lemma 5.3.

When there exists a min-cut of size 3 as given in CASE-4 (For some
$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 and
${v_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}\subset{v_{1}}^{\downarrow}$)
then the cut edges can be found in $O(D^{2})$ time.

###### Proof.

By Lemma 4.9, each node $a$ knows
$H_{{a}^{\downarrow}}^{v}=\gamma({a}^{\downarrow},{v}^{\downarrow})$ for all
$v\in\mathcal{A}\left(a\right)$. Further, for any node $a\in V\setminus r$ we
want to make sure that for any two nodes
$v,u\in\mathcal{A}\left(v\right)\setminus\left\\{a,r\right\\}$, node $a$ knows
$H_{{u}^{\downarrow}}^{v}$ if $\ell\left(u\right)>\ell\left(v\right)$. For
this, each node $x$ at level $i$ has $i-1$ such quantities to broadcast to its
descendants in ${x}^{\downarrow}$. This is similar to _Broadcast Type-2_ and
takes $O(D^{2})$ rounds. After this step every node $x$ knows
$H_{{y}^{\downarrow}}^{z}$ for all
$y,z\in\mathcal{A}\left(x\right)\setminus\left\\{r,x\right\\}$ and
$\ell\left(y\right)>\ell\left(z\right)$. Now at each node $x$, to determine if
$\left\\{(\pi\left(x\right),x),(\pi\left(y\right),y),(\pi\left(z\right),z)\right\\}$
is a min-cut, node $x$, checks if
$\eta(x)-1=H_{{x}^{\downarrow}}^{y}+H_{{x}^{\downarrow}}^{z}$ and
$\eta(y)-1=H_{{y}^{\downarrow}}^{z}+H_{{x}^{\downarrow}}^{y}$ and
$\eta(z)-1=H_{{x}^{\downarrow}}^{z}+H_{{y}^{\downarrow}}^{z}$ ∎

For other cases the problem boils down to efficiently computing the required
quantities as per Lemma 3.5 and 3.6 and communicating them to at least one
node in the network, then this node can make the required decision about the
min-cut of size 3. Unfortunately, simple broadcast and convergecast techniques
do not seem plausible for the cases which are left. This is because of the
arbitrary placements of the nodes in the tree.

In the remaining part of this chapter, we introduce two new techniques which
will take care of this. In Section 5.1, we give Sketching Technique for
CASE-3,CASE-6 and CASE-7. Further, in Section 5.2, we give Layered Algorithm
which is enough to find the min-cut as given by CASE-5 if it exists.

###  5.1 Graph Sketching

In this section, we will introduce our graph sketching technique. Recall from
Lemma 3.5 and Lemma 3.6 that to make a decision about min-cut of size $3$, a
node requires certain information about other nodes. The whole graph has as
many as $n$ nodes. It will be cost ineffective for every node to know the
details about each of $n$ nodes. We introduce sketching technique, which
reduces the number of nodes, any particular node has to scan, in order to find
the required quantities to make a decision about the min-cut.

A sketch is defined for all the nodes in the network. If there exists a min-
cut, at least some node $v$, can make the decision regarding it using its
sketch or appropriate sketch of other nodes communicated to it. In this
section, first we will give the motivation behind the use of sketch, then in
Subsection 5.1.1, we will define sketch and introduce related notations. Here
we will prove that the size of the sketch is not large. Later in Subsection
5.1.2, we will give the algorithm to compute the sketch and in Subsection
5.1.3, we will showcase the application of graph sketch in finding a min-cut
as given by CASE-3, CASE-6 and CASE-7. Before going to the formal notation of
the sketch definition, we will describe algorithmic idea for these cases.

First, we begin with CASE-3. Imagine that
$\left\\{(\pi\left(u\right),u),(\pi\left(v\right),v),e\right\\}$ is a min-cut
of size $3$, for some nodes $v,u\in V\setminus r$ such that
${v}^{\downarrow}\cap{u}^{\downarrow}=\emptyset$ and a non-tree edge $e$ as
given by CASE-3 and shown in Fig. 5.2 (A). Now imagine node $u$ has to make a
decision of this min-cut, then as per Lemma 3.5, it will require information
about $\eta(v),\gamma({u}^{\downarrow},{v}^{\downarrow})$. But upfront, node
$u$ has no idea that it is part of such a min-cut and there exists some other
node $v$, because it only has local information. Moreover, there are, as many
as $n$ nodes, in the whole network which is lot of information for node $u$ to
look at and is cost inefficient. Our sketching technique brings down the size
of the set of nodes which any node $u$ has to scan to make a decision about a
min-cut as give by CASE-3. Let
$\overline{\mathcal{N}}(A)\triangleq\left\\{y\mid x\in A,y\notin A,(x,y)\in E\
\text{is a non-tree edge}\right\\}$. We make two simple observations:

  1. i)

node $u$ needs to search only the paths from the root $r$ to all nodes
$y\in\overline{\mathcal{N}}({u}^{\downarrow})$ shown in Fig. 5.2 (B).

  2. ii)

such paths can be significantly trimmed: for instance as shown in Fig. 5.2
(A), $\left\\{(\pi\left(u\right),u),(v,v_{1}),e\right\\}$ cannot be a min-cut
because removing these edges does not partition the vertex set into two.

Figure 5.2: Demonstration of Sketching Technique for CASE-3. Each part in the
above figure is a snippet of the tree. Edges with dashed stroke style are non-
tree edges. Red edges are cut edges. Shaded region with vertices denote vertex
sets.

Based on the above two simple observation, we can see that node $u$ can limit
its scan of finding some node $x$ and subsequently
$\eta(x),\gamma({x}^{\downarrow},{u}^{\downarrow})$ to the bold path shown in
Fig. 5.2 (C). Our sketch exactly computes this. We will give details about it
in the later part of this section. The idea for CASE-6 is similar to the one
demonstrated here.

To find a min-cut as given by CASE-7, we will use a different idea called
_reduced sketch_. Recall that, a min-cut as given by CASE-7 is as follows: for
$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_{3}}^{\downarrow}\subset{v_{2}}^{\downarrow}$,
${v_{1}}^{\downarrow}\cap{v_{2}}^{\downarrow}=\emptyset$ such that
${v_{1}}^{\downarrow}\cap{v_{3}}^{\downarrow}=\emptyset$. Here we use the
characterization given in Lemma 3.6 which requires that at least one node
knows 6 quantities
$\eta(v_{1}),\eta(v_{2}),\eta(v_{3}),\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow})$.

In this case, we use a modified sketch. For any node $v$, our algorithm
ensures that each node $c\in{v}^{\downarrow}$ have information about
strategically truncated and trimmed paths from root $r$ to all the vertices in
the set $\overline{\mathcal{N}}({v}^{\downarrow}\setminus{{c}^{\downarrow}})$.
The same is illustrated in Fig. 5.3. The pictorial representation of this case
shown in Fig. 5.3 (A). Our algorithm makes sure that node $v_{3}$ (see that
$v_{3}\in v_{2}^{\downarrow}$) has information about the nodes in the bold
path (specially truncated and trimmed paths from root to nodes in
$\overline{\mathcal{N}}(v_{2}^{\downarrow}\setminus v_{3}^{\downarrow})$)
shown in Fig. 5.3 (C). The intermediate step is shown in Fig. 5.3 (B). Also,
coupling it with Lemma 4.9 node $v_{3}$ knows
$H_{{v_{3}}^{\downarrow}}^{v_{2}}=\gamma({v_{3}}^{\downarrow},{v_{2}}^{\downarrow})$.

Figure 5.3: Motivation for Sketching Technique in CASE-7. Edges with dashed
stroke style are non-tree edges. Shaded region with vertices denote vertex
sets.

In the next subsection, we will give a formal definition of _sketch_ and
_reduced sketch_. We will give the definition for a general spanning tree $T$.
The sketch is defined for a parameter $k$ which governs the number of branches
which can be included in the sketch. Further, we will give distributed
algorithms to compute sketch and reduced sketch.

####  5.1.1 Definition of Sketch

For any node $x$, let $\rho_{T}(x)$ represent the unique path from root $r$ to
the node $x$ in tree $T$. Further for any vertex set $A\subseteq V$, let
$\mathcal{P}_{T}(A)\triangleq\left\\{\rho_{T}(x)\mid x\in A\right\\}$.
Basically, $\mathcal{P}_{T}(A)$ is a set of paths. We say that a tree path
$\rho_{T}(x)$ is parallel to a tree edge $e=(a,b)$, if
${x}^{\downarrow{T}}\cap{a}^{\downarrow{T}}=\emptyset$ and
${x}^{\downarrow{T}}\cap{b}^{\downarrow{T}}=\emptyset$. Also, for any vertex
set $A\subset V$ and a tree $T$ recall that
$\overline{\mathcal{N}}_{T}(A)=\left\\{y\mid x\in A,(x,y)\in E,(x,y)\text{ is
a non-tree edge}\right\\}$.

Now, we define canonical tree which is the first structure towards defining
sketch. The sketch which we will define is nothing but a truncation of this
canonical tree. For any node $v$, the canonical tree is the graph-union of
paths from the root $r$ to non-tree neighbors of node $v$. This notation for a
canonical tree is also overloaded for a vertex set as well and formally
defined below.

######  Definition 5.4 (Canonical Tree).

Canonical tree of a node $v$ is a subtree of some spanning tree $T$, denoted
by $R_{T}(v)$ and formed by union (graph-union operation) of tree paths in
$\mathcal{P}_{T}\left(\left\\{v\cup\overline{\mathcal{N}}_{T}\left(\left\\{v\right\\}\right)\right\\}\right)$.
Canonical tree of a vertex set ${v}^{\downarrow{T}}$ is denoted by
$R_{T}({v}^{\downarrow{T}})$ and formed by union of the paths in
$\mathcal{P}_{T}\left(\left\\{v\cup\overline{\mathcal{N}}_{T}({v}^{\downarrow{T}})\right\\}\right)$.

Further, we also define a reduced canonical tree. We use the same notation
since the idea is same.

######  Definition 5.5.

Let $v$ be an internal (non-leaf and non-root) node of a tree $T$. Let
$c\in{v}^{\downarrow{T}}$, we define the reduced canonical tree denoted by
$R_{T}({v}^{\downarrow{T}}\setminus{c}^{\downarrow{T}})$ and formed by union
of the paths in
$\mathcal{P}_{T}\left(\left\\{v\cup\overline{\mathcal{N}}_{T}({v}^{\downarrow{T}}\setminus{c}^{\downarrow{T}})\right\\}\right)$

We define sketch as the truncation of the canonical tree and give an algorithm
that can compute it in $O(D^{2})$ rounds. A canonical tree could be of very
large size. Thus its truncation is required. To characterize this truncation
we will use branching number as defined in Definition 5.6. Let
$\operatorname{firstBranchNode}(T^{\prime})$ of any rooted tree $T^{\prime}$
be the branch node (a node which has at least two children in a tree
$T^{\prime}$) closest to root. If the tree $T^{\prime}$ has no branch node
then $\operatorname{firstBranchNode}(T^{\prime})$ is the root itself.

######  Definition 5.6 (Branching Number).

For any tree $T^{\prime}$, the branching number of a node $b$ in tree
$T^{\prime}$ is denoted by $\mathcal{\xi}_{{T^{\prime}}}\left(b\right)$. It is
defined as

$\mathcal{\xi}_{{T^{\prime}}}\left(b\right)\triangleq\begin{cases}1&\ell_{T^{\prime}}\left(b\right)\leq\ell_{T^{\prime}}\left(x\right)\
\&\ x\neq root(T^{\prime})\\\ 2&{b}={x}=root(T^{\prime})\\\
deg_{{}_{T^{\prime}}}(\pi_{{T^{\prime}}}\left(b\right))+\mathcal{\xi}_{{T^{\prime}}}\left(\pi_{{T^{\prime}}}\left(b\right)\right)-2&\ell_{T^{\prime}}\left(b\right)>\ell_{T^{\prime}}\left(x\right)\\\
\end{cases}$

where $x=\operatorname{firstBranchNode}(T^{\prime})$.

The aforementioned definition is illustrated through examples in Figure 5.4.
Basically, for any given tree $T^{\prime}$, branching number of any node in
the tree is a function of number of splits in paths from root to that node.

Figure 5.4: Illustration of branching number on two separate trees $T_{1}$ and
$T_{2}$

We will now make a simple observation about branching number and give a
characterizing lemma regarding the size of the canonical tree.

######  Observation 5.7.

Let $v$ be a node and $c\in\operatorname{children}_{T}(v)$. Let $b\in
R_{T}({c}^{\downarrow{T}})$, then
$\xi_{R_{T}({c}^{\downarrow{T}})}(b)\leq\xi_{R_{T}({v}^{\downarrow{T}})}(b)$.

###### Proof.

The canonical tree $R_{T}({c}^{\downarrow{T}})$ of any node
$c\in\operatorname{children}_{T}(v)$ is the subtree of the canonical tree
$R_{T}({v}^{\downarrow{T}})$. Hence the observation. ∎

######  Lemma 5.8.

For any tree $T^{\prime}$, the number of nodes in the tree that has branching
number less than $k$ is $O(2^{k}Depth(T^{\prime}))$.

###### Proof.

In the worst case $T^{\prime}$ may be a binary tree. Then each branching node
in the tree will have a degree $3$ and on the path beyond that branching node
will have branching number one more than the parent (by the definition of
branching node). On every branching node there are two paths which split in
the tree $T^{\prime}$. Thus we may have as many as $O(2^{k})$ different
branching paths. Each path may be $O(Depth(T^{\prime}))$ long thus we have
$O(2^{k}Depth(T^{\prime}))$ such nodes. ∎

We now define graph-sketch of a node which is defined based on the canonical
tree and comes with a parameter $k$ on which the truncation is based. We
define the truncation of a tree as below.

######  Definition 5.9.

For some tree $T^{\prime}$ and a number $k$,
$\operatorname{trunc}(T^{\prime},k)$ is an sub-tree of $T^{\prime}$ induced by
vertices with branching number less than or equal to $k$.

Our graph sketch will be called as $k$-Sketch because it comes with a
parameter $k$ on which the truncation is based. For every node in the
$k$-sketch, meta information is also added. We define the $k$-Sketch of a node
as below.

######  Definition 5.10 ($k$-Sketch).

For any node $v$ and a spanning tree $T$, let
$R^{\prime}=\operatorname{trunc}(R_{T}({v}^{\downarrow{T}}),k)$. The
$k$-Sketch of a node $v$ w.r.t. the spanning tree $T$ is denoted as
$\mathcal{S}_{T}^{k}(v)$ and it is defined as
$\mathcal{S}_{T}^{k}(v)\triangleq\left\\{R^{\prime}\cup\left\\{\langle
u:\eta_{T}(u),\pi_{{T}}\left(u\right),\gamma\left({v}^{\downarrow{T}},{u}^{\downarrow{T}}\right)\rangle\
\forall u\in R^{\prime}\right\\}\right\\}$

Basically $k$-Sketch is a truncated canonical tree packaged along with the
meta information $\langle
u:\eta_{T}(u),\pi_{{T}}\left(u\right),\gamma\left({v}^{\downarrow{T}},{u}^{\downarrow{T}}\right)\rangle$
for each node $u$ in the truncated tree.

We will give an algorithm to compute $k$-Sketch for every node $v\in V$ in the
next sub-section and further showcase the application of $k$-Sketch to find a
min-cut if it exists as given by CASE-3 and CASE-6. Similar to $k$-Sketch of a
node $v$ we define the reduced $k$-Sketch which is based on the reduced
canonical tree. This will be used to find a min-cut if it exists as given by
CASE-7.

######  Definition 5.11 (Reduced $k$-Sketch).

Let v be an internal node of a spanning tree $T$. Let
$c\in{v}^{\downarrow{T}}$ and let
$R^{\prime}=\operatorname{trunc}(R_{T}({v}^{\downarrow{T}}\setminus{c}^{\downarrow{T}}),k)$.
The reduced $k$-Sketch of a node $v$ and $c$ w.r.t. the spanning tree $T$ is
denoted as ${\mathcal{S}}_{T}^{k}(v,c)$ and it is defined as
${\mathcal{S}}_{T}^{k}(v,c)\triangleq\left\\{R^{\prime}\cup\left\\{\langle
u:\eta_{T}(u),\pi_{{T}}\left(u\right),\gamma\left({v}^{\downarrow{T}}\setminus{c}^{\downarrow{T}},{u}^{\downarrow{T}}\right)\rangle\
\forall u\in R^{\prime}\right\\}\right\\}$

We know give the following Lemma about the size of the $k$-Sketch.

######  Lemma 5.12.

For any spanning tree $T$, the k-Sketch of a node $v$,
$\mathcal{S}_{T}^{k}(v)$ w.r.t. $T$ is of size $O(2^{k}Depth(T)\log n)$ bits.

###### Proof.

For any arbitrary node $u\in\mathcal{S}_{T}^{k}(v)$, the sketch contains a
three tuple
$\langle\eta_{T}(u),\pi_{{T}}\left(u\right),\gamma\left({v}^{\downarrow{T}},{u}^{\downarrow{T}}\right)\rangle$.
Here
$\eta_{T}(u),\gamma\left({v}^{\downarrow{T}},{u}^{\downarrow{T}}\right)\leq|E|=O(n^{2})$
and can be represented in $O(\log n)$ bits. Thus the three tuple is of $O(\log
n)$ bits. Now by Lemma 5.8 it is clear that $\mathcal{S}_{T}^{k}(v)$ is of
size $O(2^{k}Depth(T)\log n)$ bits. ∎

######  Corollary 5.13.

For any spanning tree $T$ and an internal node $v$ and some
$c\in{v}^{\downarrow{T}}$ the reduced $k$-Sketch ${\mathcal{S}}_{T}^{k}(v,c)$
w.r.t. $T$ is of size $O(2^{k}Depth(T)\log n)$ bits.

The $k$-Sketch of a node will be used to find a min-cut as given by CASE-3 and
CASE-6. Whereas the reduced $k$-Sketch will be used to find a min-cut as given
by CASE-7. In the subsequent section, we will give algorithms to compute
$k$-Sketch and the reduced $k$-Sketch. We will work with the fixed BFS tree
$\mathcal{T}$ and for simplicity in the notations the $\mathcal{T}$ will be
skipped from subscript or superscript.

####  5.1.2 Algorithm to Compute Sketch

In this subsection, we will give distributed algorithms to compute $k$-Sketch
and the reduced $k$-Sketch. We will prove that our algorithm takes $O(D^{2})$
rounds. The idea to compute sketch is as follows: Each node computes its own
$k$-Sketch (which is of size $O(D)\log n$ bits) and communicates the same to
the parent. The parent node after receiving the sketch from all the children
computes its own sketch and communicates the same further up. This process
continues and at the end each node has its $k$-Sketch. Here we will use
Observation 5.7, to argue that the sketch received from children is enough for
a node to compute its sketch.

######  Lemma 5.14.

For all $v\in V$, $\mathcal{S}^{k}(v)$ can be computed in $O(D^{2})$ rounds.

###### Proof.

We describe a detailed algorithm to compute this in Algorithm 7. In Line 7,
Algorithm 7 calculates
$\mathcal{P}\left(\left\\{v\cup\overline{\mathcal{N}}(v)\right\\}\right)$
which as per the definitions is the tree paths of the non-tree neighbors of
$v$ including $\rho(v)$.

1 _Algorithm to be run on each node $a$_

Output: k-Sketch $\mathcal{S}^{k}(a)$

2 _Past Knowledge_

3 Each node $u\in V$ knows $\ell\left(u\right)$ and $\eta(u)$ from previous
section

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

5 $\overline{\mathcal{N}}(a)\leftarrow\left\\{b\mid(a,b)\in E,(a,b)\ \text{is
a non-tree edge}\right\\}$

6 for  _all $b\in\overline{\mathcal{N}}(a)$_ parallely do

7 send tuples $\langle\ell\left(u\right),\eta(u),u\rangle$ for all
$u\in\mathcal{A}\left(a\right)$ to $b$

$\mathcal{P}\leftarrow\left\\{\rho(a)\right\\}$ // $\rho(a)$ can be computed
easily because $a$ has all nodes in $\mathcal{A}\left(a\right)$

8 for  _all $b\in\overline{\mathcal{N}}(a)$_ parallely do

9 for  _all $u\in\mathcal{A}\left(b\right)$_ do receive tuples
$\langle\ell\left(u\right),\eta(u),u\rangle$

10 Construct the path $\rho(b)$ using the information

11 $\mathcal{P}\leftarrow\mathcal{P}\cup\rho(b)$

12

13 perform graph union of all the paths in $\mathcal{P}$ and form canonical
tree $R(a)$

14 for  _all nodes $u\in R(a)$_ do

15 if  _$u\in\mathcal{A}\left(a\right)$_ then
$\gamma(a,{u}^{\downarrow})=H_{a}^{u}$

16 else $\gamma(a,{u}^{\downarrow})=|\left\\{b\mid
b\in\overline{\mathcal{N}}(a),u\in\mathcal{A}\left(b\right)\right\\}|$

17 include the tuple $\langle
u:\eta(u),\pi\left(u\right),\gamma(a,{u}^{\downarrow})\rangle$ for the node
$u\in R(a)$

18 if  _$a$ is an internal node_ then wait until $\mathcal{S}^{k}(c)$ is
received for all $c\in\operatorname{children}(a)$

19 $S\leftarrow R(a)\cup_{c\in\operatorname{children}(a)}\mathcal{S}^{k}(c)$

20 perform graph union of all trees in $S$ to form a tree $T$

21 for  _node $u\in T$_ do

22 compute branching number $\mathcal{\xi}_{{T}}\left(u\right)$ as per the
definition

23 if  _$\mathcal{\xi}_{{T}}\left(u\right) >k$ and $u\in{v}^{\downarrow}$_
then

24 remove node $u$ from $T$

25

26 for  _node $u\in T$_ do

27 compute $\gamma({a}^{\downarrow},{u}^{\downarrow})$ by adding appropriately
from all $T^{\prime}\in S$

28

29 Construct $\mathcal{S}^{k}(a)$ using $T$ by including $\langle
u:\eta(u),\pi\left(u\right),\gamma({a}^{\downarrow},{u}^{\downarrow})\rangle$
for all node $u\in T$

30 Send $\mathcal{S}^{k}(a)$ to $\pi\left(a\right)$

Algorithm 7 Distributed Algorithm for Computing $k$-Sketch

This can be computed easily because each non-tree neighbor sends all its
ancestors and their associated meta information. Having calculated
$\mathcal{P}\left(\left\\{v\cup\overline{\mathcal{N}}(v)\right\\}\right)$,
then it is easy to compute the sketch tree $R(v)$ by Definition 5.4. Now if a
node is an internal node we again need to perform a graph union of other
sketches received from children. This is also trivial and it is guaranteed
that we will not lose any node here because of Observation 5.7. Further
branching number is computed for all the nodes and those nodes which do not
satisfy the condition of branching number are removed to form the sketch. Also
among the three tuples of meta information two remain fixed from the sketch of
children and $\gamma({u}^{\downarrow},{v}^{\downarrow})$ for a node
$u\in\mathcal{S}^{k}(v)$ can be computed by appropriate addition.

##### Time Requirements

In Algorithm 7, communication between any two nodes occur only in line 7, 7
and 7. In line 7, only $O(D)$ rounds are taken because a node has at most
$O(D)$ ancestors in the BFS tree $\mathcal{T}$. Similarly, line 7 also takes
$O(D)$ rounds because each of the neighbors also has $O(D)$ ancestors and the
transfer of the three tuples from each of the neighbors happen in parallel.
Further in line 7, a node $a$ waits to recieve all the sketch from its
children. From Lemma 5.12, we know that the size of the sketch is $O(D\log n)$
bits when the tree in action is a BFS tree. Now a node at level $l$ will wait
for all the sketch from its children which are at level $l+1$ and they inturn
depend on all the children which are at level $l+2$ and so on. Thus line 7
takes atmost $O(D^{2})$ rounds. ∎

In Lemma 5.14, we gave an algorithm for computing the $k$-Sketch. We will now
move toward an algorithm to find a reduced sketch. There are two steps towards
these details of which are given in Observation 5.15 and Lemma 5.16.

######  Observation 5.15.

For a constant $k$. For any internal node $a$, and
$c^{\prime}\in\operatorname{children}(a)$, ${\mathcal{S}}^{k}(a,c^{\prime})$
can be computed at node $a$ in $O(D^{2})$ rounds.

###### Proof.

Basically, the idea here is not to include the sketch received from child $c$,
while computing the sketch of node $a$ and the resultant becomes the reduced
sketch ${\mathcal{S}}^{k}(v,c)$. To do this, we just need to change Line 7 in
Algorithm 7 to $\mathcal{S}\leftarrow
R(a)\cup_{c\in\operatorname{children}(a)\setminus\left\\{c^{\prime}\right\\}}\mathcal{S}^{k}(c)$
for each $c^{\prime}\in\operatorname{children}(a)$ and this enables the
computation ${\mathcal{S}}^{k}(a,c^{\prime})$ at node $a$. ∎

######  Lemma 5.16.

For a fixed $k$, there exists a $O(D^{2})$ round algorithm such that all nodes
$x$ can compute ${\mathcal{S}}^{k}(v,c)$ for all
$v\in\mathcal{A}\left(x\right)$.

###### Proof.

For any internal node $v\in V$, we ensure that for all
$c\in\operatorname{children}(v)$ the reduced k-Sketch ${\mathcal{S}}^{k}(v,c)$
is downcasted to all the nodes in ${c}^{\downarrow}$. This takes $O(D^{2})$
rounds. After this step every node $x$ at level $\ell\left(x\right)$ has the
sketch ${\mathcal{S}}^{k}(a,b)$ for any node $a,b$ at level $i$ and $i+1$ for
all $i\in[1,l-1]$ and $a,b\in\mathcal{A}\left(a\right)$. Now based on this we
will show that node $x$ can compute ${\mathcal{S}}^{k}(v,x)$ for all
$v\in\mathcal{A}\left(x\right)$ as per Algorithm 8.

Each node $x\in V\setminus r$ has to perform some local computation based on
the various reduced sketch received earlier. For $1\leq
i\leq\ell\left(x\right)-1$ let $\mathcal{S}_{i}={\mathcal{S}}^{k}(a,b)$ when
$a=\alpha(x,i)$ and $b=\alpha(x,i+1)$ (recall that $\alpha(x,l)$ is the
ancestor of node $x$ at level $l$). For some node $v=\alpha(x,l)$ which is the
ancestor of node $x$ at some level $l<\ell\left(x\right)$; to compute
${\mathcal{S}}^{k}(v,x)$ node $x$ uses $\mathcal{S}=\cup_{l\leq
j\leq\ell\left(x\right)-1}\mathcal{S}_{j}$. Here $\mathcal{S}$ is basically a
set of Sketches. Note that any two sketch in the set $\mathcal{S}=\cup_{l\leq
j\leq\ell\left(x\right)-1}\mathcal{S}_{j}$ are overlapping. That is they have
information about disjoint vertex sets. The rest of the steps are exactly same
as given in Algorithm 7 and are described in detail in Algorithm 8

Input: ${\mathcal{S}}^{k}(a,b)$ for any node $a,b$ at level $i$ and $i+1$ such
that $1\leq i\leq\ell\left(x\right)-1$

Output: ${\mathcal{S}}^{k}(v,x)$ for all $v\in\mathcal{A}\left(x\right)$

1 for  _$1\leq i\leq\ell\left(x\right)-1$_ do
$\mathcal{S}_{i}\leftarrow{\mathcal{S}}^{k}(a,b)$ when $a=\alpha(x,i)$ and
$b=\alpha(x,i+1)$

// recall that $\alpha(x,l)$ is the ancestor of node $x$ at level $l$

2 for  _$1\leq i\leq\ell\left(x\right)-1$_ do

3 $v=\alpha(x,i)$

4 $S\leftarrow\cup_{i\leq j\leq\ell\left(x\right)-1}\mathcal{S}_{j}$

5 perform graph union of all trees in $\mathcal{S}$ to form a tree $T$

6 compute branching number $\mathcal{\xi}_{{T}}\left(u\right)\ \forall u\in T$
as per the definition

7 for  _node $u\in T$_ do

8 if  _$\mathcal{\xi}_{{T}}\left(u\right) >k$ and $u\in{v}^{\downarrow}$_ then

9 remove $u$ from $T$

10

11 for  _node $u\in T$_ do

12 compute
$\gamma({v}^{\downarrow}\setminus{x}^{\downarrow},{u}^{\downarrow})$ by adding
appropriately from all $T^{\prime}\in S$

13

14

15 Construct ${\mathcal{S}}^{k}(v,x)$ using $T$ by including $\langle
u:\eta(u),\pi\left(u\right),\gamma({v}^{\downarrow}\setminus{x}^{\downarrow},{u}^{\downarrow})\rangle$
for all node $u\in T$

16

Algorithm 8 To be run on all node $x\in V\setminus\left\\{r\right\\}$

∎

####  5.1.3 Application of graph sketch

Now we will describe the application of graph sketch to find a min-cut of size
$3$ if it exists as given by CASE-3, CASE-6 and CASE-7. We prove the same in
Lemma 5.17. Here, CASE-3 is a direct application of $3$-Sketch; in CASE-6 we
will be required to move $3$-Sketch in a strategic way and in CASE-7 reduced
$2$-Sketch will be used. We give further details of each of the cases in Lemma
5.17, 5.18 and 5.20.

For any two nodes $v_{1},v_{2}$, let $\operatorname{LCA}_{T}(v_{1},v_{2})$ be
the lowest common ancestor of node $v_{1}$ and $v_{2}$ in tree $T$.

######  Lemma 5.17.

For some $v_{1},v_{2}\in V\setminus r$ and a non-tree edge $e$, if
$\left\\{(\pi\left(v_{1}\right),v_{1}),(\pi\left(v_{2}\right),v_{2}),e\right\\}$
is a min-cut as given in CASE-3, then node $v_{1}$ can make a decision about
the said min-cut using $\mathcal{S}^{3}(v_{1})$.

###### Proof.

As per Lemma 3.5, we know that node $v_{1}$ can decide for such a min-cut if
it knows three quantities: $\eta(v_{1}),\eta(v_{2})$ and
$\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow})$. Also, for any node $u,v$,
we know that if there is a node $u\in\mathcal{S}^{3}(v)$ then the sketch also
contains $\eta(u),\gamma({u}^{\downarrow},{v}^{\downarrow})$. And every node
$v$ in the network knows $\eta(v)$ from previous section. Thus here to prove
this lemma we have to prove that node $v_{2}\in\mathcal{S}^{3}(v_{1})$. Then
node $v_{1}$ can enumerate through all the nodes in $\mathcal{S}^{3}(v_{1})$
which are not in $\mathcal{A}\left(v\right)$ and apply the condition of Lemma
3.5 to test if there exists such a min-cut.

Figure 5.5: Illustrating different types of sub-cases which might occur when
there exists a min-cut of size $3$ as in CASE-3. The figures presented here
are tree snippets. In each of the sub-cases we demonstrate the $3$-Sketch as
computed by 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. Here all the edges that go out of the vertex set
${v_{1}}^{\downarrow}$ have their other end points in the vertex set
${v_{2}}^{\downarrow}$ barring one non-tree edge $e$ in (B) and (C). The
important fact here is that in all the different cases
$v_{2}\in\mathcal{S}^{3}(v_{1})$

.

We will now show that if such a min-cut exists then node
$v_{2}\in\mathcal{S}^{3}(v_{1})$. As illustrated in Fig. 5.5 for all the
different sub-cases node $v_{2}\in\mathcal{S}^{3}(v_{1})$. In (A) when the
other non-tree edge $e$ has one end-point in ${v_{2}}^{\downarrow}$ then the
branching number of $v_{2}$ in the sketch-tree $R({v_{1}}^{\downarrow})$ is
$\mathcal{\xi}_{{R({v_{1}}^{\downarrow})}}\left(v_{2}\right)=2$ thus
$v_{2}\in\mathcal{S}^{3}(v_{1})$. Both (B) and (C) are similar in terms of the
fact that the non-tree cut edge $e$ has the other endpoint in
${v_{1}}^{\downarrow}$ but differ in terms of the branching node. Nevertheless
here also $\mathcal{\xi}_{{R({v_{1}}^{\downarrow})}}\left(v_{2}\right)=3$ thus
$v_{2}\in\mathcal{S}^{3}(v_{1})$

∎

######  Lemma 5.18.

For some $v_{1},v_{2},v_{3}\in V\setminus r$, let
${v_{1}}^{\downarrow},{v_{2}}^{\downarrow},{v_{3}}^{\downarrow}$ be pair wise
mutually disjoint. If there exists a min cut as in CASE-6 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.

For such a min-cut to exists then at least two of
$\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$
need to be non-zero otherwise the vertex sets
${v_{1}}^{\downarrow}\cup{v_{2}}^{\downarrow}\cup{v_{3}}^{\downarrow}$ may not
form a connected component. WLOG here we may have two non-isomorphic cases as
illustrated in Fig. 5.6.

(a) One of
$\gamma({v_{1}}^{\downarrow},{v_{2}}^{\downarrow}),\gamma({v_{1}}^{\downarrow},{v_{3}}^{\downarrow}),\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})$
is zero. WLOG let $\gamma({v_{2}}^{\downarrow},{v_{3}}^{\downarrow})=0$

(b) All three of