Semirandom Planted Bipartite Subgraphs

[13] proposed a model in which a $d$-regular bipartite graph is planted on a set $S$ of size $k$ in $G$ and rest of the edges are added independently with probability $p$, they designed an algorithm which recovers the planted bipartite subgraph with high probability when $k={\mathrm{\Omega }}_p(\sqrt{n\log n})$. Their algorithm also works for monotone adversary i.e. their algorithm can also recover the planted bipartite subgraph even if arbitrary edges are added in $G[V\setminus S]$ with addition to the edges that are already randomly generated. They show that the natural SDP formulation of this problem is integral. [14] studied this problem without monotone adversary and gave an simple spectral algorithm to recover when $k=\mathrm{\Omega }(\sqrt{n})$. [9] also study a natural extension of their semirandom model for $2$-coloring (defined earlier in this section) to 3-coloring. Assuming that there is an algorithm to color 3-colorable graphs using $n^{\theta }$ colors, they gave an algorithm to compute a set of size $(1-ϵf(p,\theta ))n$ (for some function $f$) and an $n^{\theta }$ coloring of it, where $(1-ϵ)n$ is the size of the planted $3$-colorable subgraph.

In [1] a polynomial time algorithm was designed for the following problem. Given a graph $G=(V,E)$ where there exists a $(1-ϵ)|V|$ size subset $U$ of $V$ such that the induced subgraph on $U$ is bipartite, produce a subset $U^{\prime }$ of $V$ of size at least $(1-O(ϵ\sqrt{\log n}))|V|$ such that the subgraph induced on $U^{\prime }$ is bipartite. In [7], for the case where the maximum degree of $G$ is $d$, they gave an algorithm to produce a subset $U^{\prime }$ of size at least $(1-O(\sqrt{ϵ\log d}))|V|$ such that the subgraph induced on $U^{\prime }$ is bipartite; assuming the Unique Games conjecture, they prove a matching (up to constant factors) hardness. [8] studied the problem when the bipartite graph induced on $U$ is a regular and low threshold-rank graph; they gave an algorithm, running in time exponential in $poly(1/ϵ)$, to recover a $(1-{ϵ}^{1/12})n$ sized subset of $U^{\prime }\subset V$ such that the graph induced on $U^{\prime }$ is bipartite. Given a graph $G=(V,E)$ in which there exists a subset $U$ of size $(1-ϵ)|V|$ such that the graph induced on $U$ is $3$-colorable. [9] designed a polynomial time algorithm to produce a subset $S\subset V$ such that $|S|\le 3\sqrt{ϵ}|V|$ and color $V\setminus S$ using $\tilde{O}(n^{0.25+O({ϵ}^{0.25})})$. They gave an algorithm to give a more general result.

In [1], the problem of Min UnCut was studied which is equivalent to the problem of removing a minimum set of edges $M$ from a graph $G=(V,E)$ such that the graph $G^{\prime }=(V,E\setminus M)$ is bipartite. [1] designed a $O(\sqrt{\log n})$ approximation algorithm based on semi definite programming. [10] gave an algorithm to delete $O(\sqrt{OPT})$ fraction of edges to obtain a bipartite graph where $OPT$ is the optimal fraction of edges in Min UnCut.

Assume $i,j,w\in S_1$ and . Then

Similarly the same will be also true for $|N_i\mathrm{\Delta }{N}_w|$ and $|N_j\mathrm{\Delta }{N}_w|$. By the formula of inclusion-exclusion, we have

Since $N_i\cup N_j\cup N_w\subseteq S_2$ and $|S_2|\le tk/(1+t)$, we have

which gives us a contradiction. Similarly if $i,j,k\in S_2$ then $N_i\cup N_j\cup N_w\subset S_1$ and $|S_1|\le k/2$. Therefore

$◀$

Call a pair of vertices $i,j\in S$ good if $⟨G_i^S,G_j^S⟩\ge \frac{k}{12/(3-t)}$, otherwise call them bad. Lemma 9 shows that all but one vertex of $S_1$ forms a good pair with some other vertex of $S_1$.

To see this define

if $S_1\setminus T$ is nonempty then choose a vertex $i$ from it. Since $i\notin T$ it means $i$ forms bad pairs with all other vertices in $S_1$. Then by Lemma 6 we can conclude that all the vertices in $S_1\setminus \{i\}$ forms good pairs in each other, so $|T|\ge |S_1|-1$. Similar argument can be applied to $S_2$. $◀$

The following lemma is taken directly from [3] which will imply that a vertex from $S$ cannot be highly correlated with many vertices of $V\setminus S$. We reproduce their proof here to make dependence on $t$ explicit since this case doesn’t arise in their setting.

Consider the $n\times k$ matrix $H$ with columns $v_1,v_2,\mathrm{\dots },v_k$. Then, by standard results in random matrix theory, ${\Vert H\Vert }_2\le O(\sqrt{n}+\sqrt{k})$ with probability $1-1/n$. Let $ℬ\subset [k]$ be such that, for every $i\in ℬ,⟨u,v_i⟩\ge \frac{k}{24/(3-t)}$. Then, by the Cauchy-Schwartz inequality, we have

On the other hand, by the choice of set $ℬ$, we have

Combining those two inequalities and rearranging, we get $|ℬ|\le O\left(\frac{{24}^2}{{(3-t)}^2}{n}^2/k^2\right)$. $◀$

For $i\in V$, define $V_i=\{j\in V|⟨G_i,G_j⟩\ge \frac{k}{18/(3-t)}\}$. We show that we can reconstruct a bipartite graph which is close to the planted bipartite subgraph using $i,j,w,l\in S$ .

We apply the Lemma 10 with $G_i^{\text{out}}$ for each $i\in S$ as a uniform random element of ${\{\pm 1\}}^{n-k}$ and by taking $u=G_j^{\text{out}}$ for any $j\in V\setminus S$. By Lemma 10, for each $j\in V\setminus S$, at most $O\left(\frac{{24}^2}{{(3-t)}^2}{n}^2/k^2\right)$ elements of $i$ of $S$ will satisfy $⟨G_i^{\text{out}},G_j^{\text{out}}⟩\ge \frac{k}{24/(3-t)}$. Using this and the fact that for all $i\in S$ and $j\in V\setminus S$, $⟨G_i^{\text{S}},G_j^{\text{S}}⟩=O(\sqrt{k\log k})$ with probability $1-1/n$, we get that there are in total $O\left(\frac{{24}^2}{{(3-t)}^2}{n}^3/k^2\right)$ pairs $(i,j)$ such that $i\in S,j\notin S$ satisfying

By Markov’s inequality, a uniformly random $i\in S$ satisfies $⟨G_i,G_j⟩\ge \frac{k}{18/(3-t)}$ for at most $O\left(\frac{{24}^2}{ϵ{(3-t)}^2}{n}^3/k^3\right)$ vertices $j\in V\setminus S$ with probability $1-ϵ$. If $k\gg O\left(\frac{{24}^2}{ϵ{(3-t)}^2}{n}^3/k^3\right)$ e.g. $k=\mathrm{\Omega }\left(\sqrt{\frac{24}{{ϵ}^{1/2}(3-t)}}{n}^{3/4}\gamma (n)\right)$ such that ${lim}_{n\to \mathrm{\infty }}\gamma (n)=\mathrm{\infty }$, then at least $k(1-ϵ)$ vertices $i$ of $S$ will satisfy $|V_i\setminus S|=O\left(\frac{k}{{\gamma }^4(n)}\right)=o(k)$, which means $V_i$ will contain at most $o(k)$ vertices not from $S$, call such a set of vertices $i$ of $S$ as $S^{\ast }$. Therefore

Note that to make the contribution from random terms small we need $\frac{k}{18/3-t}-\frac{k}{24/3-t}>\mathrm{\Omega }(\sqrt{k\log k})$. Therefore we also need $k=\mathrm{\Omega }(\log k/{(3-t)}^2)$.

In [3] because $S$ was a clique, the above argument implies that for a vertex $i\in S^{\ast },V_i$ contains the whole of $S$ and $o(k)$ vertices from $V\setminus S$. To see this, observe that each vertex $j\in S$ will satisfy $⟨G_i,G_j⟩=k\pm O(\sqrt{n\log n})\ge k/6$ and all but $o(k)$ vertices of $V\setminus S$ will not be in $V_i$ because $i\in S^{\ast }$. Our goal is to extend this idea to recover bipartite subgraphs. We show that in SRPB$(n,k,1/2,t)$ we can recover $1-O(ϵ)$ fraction of vertices of $S$ using at most $4$ vertices of $S$.

Let $i\in S_1\cap S^{\ast }$. Intuitively Lemma 6 gives us that if $V_i$ doesn’t contain all vertices of $S_1$ i.e. if $S_1\setminus V_i\ne \varphi$, then any two vertices $j,w\in S_1\setminus V_i$ will satisfy $⟨G_i^S,G_w^S⟩\ge k/\frac{12}{3-t}$ so $V_j\supset S_1\setminus V_i$ i.e. $V_i\cup V_j\supset S_1$. But we also need $j$ to be in $S^{\ast }$ for $|(V_i\cup V_j)\setminus S|=o(k)$ which brings us to two cases.

Assume that $(S_1\setminus V_i)\setminus (S\setminus S^{\ast })\ne \varphi$. Then by Lemma 6, any vertex $j\in (S_1\setminus V_i)\setminus (S\setminus S^{\ast })$ (i.e. $j\notin V_i$ and $j\in S_1\cap S^{\ast }$) will satisfy $V_j\supset S_1\setminus V_i$ because for any other vertex $w\in S_1\setminus V_i$, it must be that , and since $⟨G_i^{\text{out}},G_w^{\text{out}}⟩=O(\sqrt{n\log n})\ll \frac{k}{36/(3-t)}$ with very high probability, it implies that . This implies that by Lemma 6 $⟨G_j^S,G_w^S⟩\ge \frac{k}{12/(3-t)}$ which means $⟨G_j,G_w⟩\ge \frac{k}{18/(3-t)}$ for any $w\in S_1\setminus V_i$, so $V_i\cup V_j\supset S_1$. Also since $j\in S_1\cap S^{\ast }$ we have $|(V_1\cup V_j)\setminus S|\le |V_i\setminus S|+|V_j\setminus S|=o(k)$.

$(S_1\setminus V_i)\setminus (S\setminus S^{\ast })=\varphi$, then $V_i$ has almost all the vertices of $S_1$ because $S_1\setminus V_i\subset S\setminus S^{\ast }$, so $|S_1\setminus V_i|\le |S\setminus S^{\ast }|=O(ϵk)$ and since $i\in S_1\cap S^{\ast }$ we have $|V_1\setminus S|=o(k)$.

Therefore either by case 1 or case 2 there exists either one or two vertices of $S_1$ such that $|S_1\setminus (V_i\cup V_j)|=O(ϵk)$ and $|(V_i\cup V_j)\setminus S|=o(k)$. Similarly we can find two vertices $w,l\in S_2$ which satisfies $|S_2\setminus (V_w\cup V_l)|=O(ϵk)$ and $(|V_w\cup V_l)\setminus S|=o(k)$, which shows that there exists at most four vertices such that $|(V_i\cup V_j\cup V_w\cup V_l)\mathrm{\Delta }S|=O(ϵk)$. $◀$

From the above four lemmas we can finish the proof of Theorem 2.

Algorithm 1 goes through all the four set of vertices and take their union. Then by Lemma 7 one of them will be close to the planted bipartite subgraph. Since Algorithm 1 enumerates over all choice of $i$, the size of list is at most $n^4$. $◀$

There exists ${\alpha }_1,{\alpha }_2\in T^{\ast }\cap \left(\genfrac{}{}{0pt}{}{S_1}{3}\right)$ such that $S_1\subset V_{{\alpha }_1}\cup V_{{\alpha }_2}$, which means that $S_1\setminus (V_{{\alpha }_1}\cup V_{{\alpha }_2})=\varphi$. Since $V_{{\alpha }_1},V_{{\alpha }_2}\in T^{\ast }\cap \left(\genfrac{}{}{0pt}{}{S_1}{3}\right)$, it implies that $|V_{{\alpha }_1}\setminus S|,|V_{{\alpha }_2}\setminus S|=o(k)$. Therefore $|(V_{{\alpha }_1}\cup V_{{\alpha }_2})\setminus S|\le o(k)$.

For all pairs of ${\alpha }_1,{\alpha }_2\in T^{\ast }\cap \left(\genfrac{}{}{0pt}{}{S_1}{3}\right)$, there exists a vertex $i_{{\alpha }_1,{\alpha }_2}\in S_1$ such that and . Note that this implies that for because $⟨G_{{\alpha }_1}^{\text{out}},G_{i_{{\alpha }_1,{\alpha }_2}}^{\text{out}}⟩=O(\sqrt{n\log n})\ll \frac{k}{18/(3-t)}$, and the same is true for ${\alpha }_2$ .