Reminder: This post contains 5100 words
· 15 min read
· by Xianbin
Edge degree constrained subgraph (EDCS) has received much attention and proved to be very useful in matching related problems. In this post, we introduce some interesting properties of EDCS in distributed settings. This post is based on [1,2,3].
Definition
\(\textbf{Definition (EDCS)}\) Given a graph \(G = (V, E)\), let \(\beta_1 \geq \beta_2 \geq 0\) be two parameters. An edge degree constrained subgraph (EDCS) \(H=({\color{blue}V}, {\color{red}E_H})\) of \(G\) satisfies the following properties.
\(\textbf{P1)}:\) For any edge \((u,v) \in E_H\): \(d_H(u) + d_H(v) \leq \beta_1\).
\(\textbf{P2)}:\) For any edge \((u,v) \in E\setminus E_H\): \(d_H(u) + d_H(v) \geq \beta_2\).
EDCS in Sampled Subgraphs
\(\textbf{Lemma 1}\) (Degree Distribution Lemma). Fix a graph \(G=(V, E)\) and two parameters \(\beta_1, \beta_2\). Let \(\beta_2 = (1-\lambda)\beta_1\). For any two subgraphs \(G_1,G_2\) that are \(\text{EDCS}(G, \beta_1,\beta_2)\), and any vertex \(v\in V\), we have
\[\lvert d_{G_1}(v) - d_{G_2}(v) \rvert = O(\log n) \sqrt{\lambda}\cdot \beta\]
\(\textbf{Theorem 1}\). Let \(G_1, G_2 \subseteq G\) be two edge sample subgraphs (selecting with probability \(p\)) for a given graph \(G= (V, E)\). Let \(\color{blue} H_1, H_2\) denote any EDCSs of \(G_1, G_2\) respectively, with parameters \((\beta, (1-\lambda)\beta)\).
Suppose, \(\beta \geq \frac{750}{\lambda^2} \ln n\), with high probability, for each \(v \in V\), we have
\[\lvert d_{H_1}(v) - d_{H_2}(v)\rvert \leq O(\log n) \sqrt{\lambda}\cdot \beta\]
\(\textbf{Theorem 2}\). Let \(G_1, G_2 \subseteq G\) be two \(\color{red}\text{vertex}\) sample subgraphs (selecting with probability \(p\)) for a given graph \(G= (V, E)\). Let \(\color{blue} H_1, H_2\) denote any EDCSs of \(G_1, G_2\) respectively, with parameters \((\beta, (1-\lambda)\beta)\).
Suppose, \(\beta \geq \frac{750}{\lambda^2} \ln n\), with high probability, for each \(\color{blue} v \in G_1\cap G_2\), we have
\[\lvert d_{H_1}(v) - d_{H_2}(v)\rvert \leq O(\log n) \sqrt{\lambda}\cdot \beta\]
\(\textbf{Lemma 1}\). For any \(\epsilon > 0\) and \(\beta \geq 1/\epsilon\), any graph \(G = (V, E)\) admits a \(EDCS(G, \beta, (1-\epsilon)\beta).\)
It is easy to state this argument, but how to prove such a thing? Let me try to do this in thirty minutes.
If I can design an algorithm to create the required EDCS for any graph, it is proved. So my job is to find this algorithm. For simplicity, let us assume that \(\beta,\epsilon\) are some constants. The first step is to obtain the first property, i.e., for any edge \((u,v)\) in EDCS, the sum of degree of \(u,v\) is at most \(\beta\). That is easy. We just randomly sample some constant number of edges for each node in \(V\). It seems that we already satisfy both properties, but there is a problem. For example, if a node has a large degree, then in the sampled subgraph, its degree can be large, which will violate the first property.
I also noticed that if we start with an empty graph, the first property and second property are already satisfied.
When I look at the definition of EDCS, I realized that one thing I did notice before. The goal of EDCS is for the matching. The edge with large degrees of endpoints should not be included in the matching, because it will reduce the chance we find a larger size of matching. If we need a data structure to contain a good matching, we should not contain such an edge. That is to say, for edges in the EDCS, we want the degrees are small and edges out of EDCS can be large.
It is better starting with an empty graph. We first add some edges trying to meet property (ii). We may need to fix the previous results, i.e., removing some edges, if the added edges violate property (i). The final thing is to show that after a certain number of steps, the procedure of fixing will stop. I know potential function might help. The question is to build such a potential function.
Time is up! I cannot figure out the potential function.
Let us check the answer.
\(\textbf{Proof}\). Start with an empty graph \(H\). ( Ha. We have it! ). If there exists an edge in \(H\) that violates property (i), we remove it. If there exists an edge in \(G\setminus H\), we add it to \(H\).
Set the potential function to be
\[\Phi = \Phi(H) :=\underbrace{(1-\frac{\epsilon}{2})\beta \sum_{u\in V} deg_H(u)}_{\text{ first term} } +\underbrace{\sum_{(u,v)\in H}-(deg_H(u) + deg_H(v))}_\text{second term}\]
( This function is what we missed. )
The maximum value of this function is at most \(O(n\beta^2)\) and the initial value is 0.
After removing an edge,
- the first term decreases by \(2\beta - \epsilon \beta\) (each node reduces one degree).
- the second term increases by at least \(\beta + 1 + \beta -1 = 2\beta\).
Therefore, \(\Phi\) increases by at least \(\epsilon \beta\) for this case.
Similarly, after adding an edge, \(\Phi\) increases by at least \(\epsilon \beta\).
So, after \(O(n\beta/\epsilon)\), the algorithm will stop. It is proved.
It is a beautiful proof.
Unfortunately, I did not figure out the potential function.
Some feelings about this potential function.
I feel that the role of this potential function is to show that no matter edge deletions or edge insertions, the potential function increases. To achieve this goal, we need experience.
Reference
[1]. Assadi, Sepehr, et al. “Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs.” Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
[2]. A. Bernstein and C. Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 692–711, 2016
[3]. Bernstein, Aaron, and Cliff Stein. “Fully dynamic matching in bipartite graphs.” Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42. Springer Berlin Heidelberg, 2015.