# Advanced Algorithm - Final

- Paper: [Distributed Weighted Min-Cut in Nearly-Optimal Time](https://dl.acm.org/doi/pdf/10.1145/3406325.3451020)

:::info
==Motivation==
- If we use BFS to find the two edges that define the minimum 2-respecting cut, we may need to go over all possible Ω(㎡)pairs of tree edges.
- It requires Ω(n 2 ) time, which is clearly too expensive.
- To get a faster algorithm, our general approach as follows:
- Use a routing trick to efficiently route information in the graph.
- Avoid using global communication over a BFS tree for all the computations.
- Our goal is to minimize the number of rounds to compute the value of the min-cut or to make every vertex realize which edges incident to it are in the min-cut.

:::

## Introduction
### A. Minimum cut (min-cut)
* cut:
* In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets.
* 把一張Grpah一分為二的所有邊的集合，稱之。
* min-cut：
* Given a graph with n vertices and m (possibly weighted) edges, a cut is a set of edges removing which **disconnects** the graph, and the weight of the cut is the total weight of the edges participating in the cut.(Weighted Min Cut)
* 給定一個加權圖𝐺，cut是一組集合邊，將graph斷開，cut的weight為在所有cut中所有邊的權重總和
* n: # of 頂點(vertices)
* D: hop直徑
* m:(可能有權重)邊
* https://blog.csdn.net/mmm_jsw/article/details/83787395

### B. CONGEST model
- LOCAL model: Every vertex can send poly(n)bits of information to each of its neighbors in each round.
- CONGEST model:
- It is one of the most studied message-passing models in the field of distributed computing.
- Every vertex can send log(n)bits of information to each of its neighbors in each round.
- For many graph problems in the CONGEST model such as minimum cut, minimum spanning tree, and single source shortest paths.
* [LOCAL and CONGEST model in graph theory](https://math.stackexchange.com/questions/3502775/local-and-congest-model-in-graph-theory)
* [Reachability and Shortest Paths in the Broadcast
CONGEST Model](https://drops.dagstuhl.de/opus/volltexte/2019/11318/pdf/LIPIcs-DISC-2019-11.pdf)

### C. Distributed min-cut
* Sequential setting :順序設置指的是最小割算法的傳統順序計算，算法是按順序逐步進行，沒有進行平行或分佈式處理。
* A Distributed min-cut such as s minimum cut, minimum spanning tree and single-source shortest paths.(Distributed algorithm)
* In each communication round each vertex sends a message of O(logn) bits to each of its neighbors which arrives at the end of the round.
* Our goal is to minimize the number of rounds to compute the value of the min-cut or to make every vertex realize which edges incident to it are in the min-cut.

### D. 2-respecting min-cut
* 2-respecting means the **2 tree edges $e,e'$** that define the minimum cut. (The cut is defined by two edges.)

## 2.1 介紹cover value
* Cov(e):
* For a tree edge e, we denote by Cov(e) the value of the cut obtained by removing e from the tree(see Figure 1), this is the **sum** of costs of **all edges** that **cross the cut**.
* This notation implies that the edges crossing the cut cover e.
* These are exactly the edges {u, v} such that e is in the unique tree path between u and v.
* 如果e是edge{u,v}唯一的tree path，則Cov(e) = Cut(e)
* 虛線點不是tree edge
* 左圖，1-respecting cut defined by e，點到點之間需透過tree edge e才能將點連起來，所以Cov(e) =10
* 右圖，2-respecting cut defined by e1, e2
* x1 只cover e1 沒有 e2
* x2 只cover e2 沒有 e1
* x3 cover e1和e2
* Cov(e,e′)= the sum of costs of all edges that cover both e and e ′.
* 計算Cov(e)的值可以在~O(D +√n)時間，paper 24


## Proposed Method
### A. Short-paths routing trick
分成兩種情況討論:
1. An edge f between P and P’
* 這裡的主要想法是就是在P和P'之間用f route訊息，然後通過聚合計算在P和P′內的cut。這樣能夠再不同路徑使用平行計算。因為claim 2.1，如果假設p中的邊都已知Cov(e)，P′中的邊都已知Cov(e')。當path的長度為O(√n)，需要O(√n)時間可以將所有cover value都傳到其中一個path上，稱為P，導致f上有O(√n)的congestion。因此我們只需計算value Cov(e,e′)。因此如果固定兩個邊，e ∈ P, e ′ ∈ P ′,表示所有cover這兩個邊的邊，有一個點在e之下，一個點在e'之下，可以連接P和P'。因此，我們可以在P內部計算成本。 在這個計算中，我們固定e′∈ P′，並為每條邊e∈P計算成本 Cov(e, e′)。這需要P的邊上有~O(1)的擁塞（擴張是O(√n))。為了計算所有e ∈ P ，使用pipeline技術，將計算過程分為多個階段，並同時處理不同的邊e，以實現O(√n)的複雜度

2. No edge between P and P
* Cov(e, e′) = 0，根據claim 2.1，只需要找Cov(e)和Cov(e′)，所以只需要在path內上計算cover值，並廣播到整個graph中。因為每條路徑廣播需要O(1)，因此可透過廣播O(√n)去比較所有沒有edge連接的pairs of path
* 結論:雖然這裡討論的是spider graph，但相同原則也可以應用於其他setting中，只要有two tree paths P, P′ of size O(√n)

### B. Structural lemma for bounding interesting paths
* 比較兩條leg，需要O(√n)，可以使用平行計算對於不相交的pair of paths。如果想要比較所有pair of paths需要Ω(n)時間，因為比較兩條leg需要在其中一個path 做聚合計算 Ω(√n)，congestion為Ω(√n)。因此如果需要將一條leg與所有√n比較，需要 Ω(n)時間。但這樣造成時間複雜度提高，為了解決，限制# of pair of paths 需要做比較，引入interesting paths(2條path存在一定關聯)的概念，一個path只對O(logn)的path有興趣，利用Short-paths routing trick加上interesting paths可以讓time為~O(√n)在spider graph做min 2-respecting cut，因為每一條leg只需要做O(logn) 計算花O(√n)時間
* Interesting paths:根據其他paper，對於每一條edge，只有少數的Ancestor to descendant paths"（祖先到后代路径)可以存在一條邊e'，使得Cut(e,e')的值最小，我們稱e對e'感興趣，if 

* 根據上述公式與spider graph的特性(每條path相互獨立且不相交)，當e對P上至少一條邊有興趣，我們稱e對spider的一條leg有興趣。根據paper[22]，我們可以得到e只能對一條leg有興趣(e∉P)，原因很簡單，因為如果e對P有興趣，則根據公式，至少有一半cover e的edge在路徑P上
* 針對上面的討論，意味著每條邊都對一條路徑感興趣，但這還不夠，原因是路徑 P 的每條邊都可能對蜘蛛的另一條腿感興趣，在這種情況下，會需要對所有路徑對運用claim 2.2 以找到min 2-respecting cut，這會浪費時間。為了克服它，我們展示了更有力的論據。我們說路徑P對路徑P'感興趣，如果路徑P中存在一條對路徑P'感興趣的邊。

* 證明2.4:(未完)因為權重是有界的，所以P只會對O(logn)不同P有興趣

* 此2.4，適用於spider graph，因為有edge disjoint特性(2條路徑沒有共享的邊)，然而其他圖不一定是這樣
* Finding interesting paths:儘管引理 2.4 限制了每條腿可能感興趣的蜘蛛的腿數，我們仍然需要按順序識別這些有趣的腿完成這個蜘蛛圖簡單案例的算法。可以使用sample，但因為sample的性質，只能找出有興趣的superset，無法確定有興趣的set，可以看到在2 Respecct cut 為˜O(D +√n)

### C. Path-partitioning lemma
- 結合Divide-and-Conquer
- 分段去算成本

## Conclusion
- In this paper, we provide an exact Õ( √n+ D)-time algorithm for computing min-cut on weighted networks.
- n:vertices
- D:hop-diameter
- Its time complexity matches the known lower bound up to polylogarithmic factors.
- At the heart of the algorithm are a routing trick and two structural lemmas regarding the structure of a minimum cut of a graph.
- Interesting path counting lemma
- Short-paths routing trick
- Path-partitioning lemma
- Our result improves the above methods that not only works on simple networks but also on general graphs.