Reminder: This post contains 1760 words
· 6 min read
· by Xianbin
This post is based on [1].
The definition of EDCS can be seen in the post EDCS Definitions.
1. EDCS for a bipartite graph
\(\textbf{Lemma 1}\). Let \(G=(L, R, E)\) be a bipartite graph and \(\epsilon < 1/2\). For \(\lambda \leq \frac{\epsilon}{4}\), \(\beta_2 \geq 2\lambda^{-1} \geq \frac{8}{\epsilon}\), and \(\beta_1 \geq (1-\lambda)\beta_2 \geq 8/\epsilon -2\), \(H:=EDCS(G, \beta_1,\beta_2)\), \(\mu(G) \leq (3/2+\epsilon)\mu(H)\).
So, let us try to prove this in one hour. For bipartite matching, we had to know the famous Hall’s Theorem.
\(\textbf{Lemma 2} \text{(Hall's Marriage Theorem)}\). A biparite graph \(G=(L, R, E)\) has a perfect graph if and only if \(\forall A\subseteq L: \lvert A\rvert \leq \lvert N(S) \rvert\) and \(\forall B\subseteq R: \lvert B\rvert \leq \lvert N(B) \rvert\).
But what if a bipartite graph does not have a perfect matching. There is a conception that is interesting.
\(\textbf{Deficiency}\). Let \(G = (V, E)\) be a graph and let \(U\) be an independent set of vertices. We use \(N_G(U)\) to denote the set of neighbors of \(U\). The deficiency of a set \(U\) is defined as
\(def_G(U) = \lvert U \rvert - \lvert N_G(U) \rvert\)
If \(G\) is a bipartite graph \(G=(L, R, E)\), we define
\(def(G;L) = \max_U def_G(U)\)
\(\textbf{Theorem 1}\). Every bipartite graph \(G=(L,R,E)\) admits a matching with size \(\mu(G) \geq \lvert L\rvert- def(G;L) = n -def(G,L).\)
To prove Lemma 1, we need to find the relationship between EDCS and the above observation. I feel EDCS is a set of sampling average edges. The degree of each node in EDCS is similar. What does that help us prove this lemma?
( After 0.5 hour ......) Oh, I cannot know how to find the relationship. Let me try to start from the conclusion. There is an obstacle: how to remove \(\max\) from the formula?
It is not easy to prove this lemma. I will try to prove this next time.
To be continued....
2. EDCS for a non-bipartite graph
Reference
[1]. Assadi, Sepehr, and Aaron Bernstein. “Towards a Unified Theory of Sparsification for Matching Problems.” 2nd Symposium on Simplicity in Algorithms. 2019.