C1: Static EDCS

April 20, 2024

• 1. EDCS for a bipartite graph
• 2. EDCS for a non-bipartite graph
• Reference

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.