论文标题
半随机图中种植的两分图的精确恢复算法
Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs
论文作者
论文摘要
在给定图中找到最大诱导的平衡二分子子图的问题是NP- hard。这个问题与找到最小的奇数循环横向的问题密切相关。 在这项工作中，我们考虑以下实例模型：从一组顶点$ v $开始，选择了$ k $ dertices的一组$ s \ subseteq v $，并在其上添加了任意的$ d $ d $ - d $ regorbul二级图； $ s \ times（v \ setminus s）$和$（v \ setminus s）\ times（v \ setminus s）$之间的边缘对之间的边缘（v \ setminus s）$。由于对于$ d = 0 $，因此问题减少了恢复种植的独立集，因此我们不希望$ k = o（\ sqrt {n}）$有效算法。这个问题是对种植平衡的双石问题的概括，在$ s $上诱导的双方图是完整的两部分图。 [LEV18]给出了一种算法，用于在$ k =ω（\ sqrt {n}）$中回收$ s $。 我们的主要结果是一种有效的算法，该算法在$ k =ω_p（\ sqrt {n \ log n}）$中恢复了（W.H.P.），以恢复种植的两分图。我们的结果也适用于天然的半随机实例模型，涉及单调对手的存在。我们的证明表明，该问题的天然SDP松弛是通过为其双重配方构建适当的解决方案而不可或缺的。我们的主要技术贡献是一种构建双重解决方案的新方法，我们将邻接矩阵的特征向量校准为双基质的特征向量。我们认为，这种方法也可能在半随机模型中适用于其他恢复问题。 当$ k =ω（\ sqrt {n}）$时，我们给出了一种算法，用于恢复其运行时间的$ s $在$ s $上诱导的小型特征值的数量中；该算法基于[KT07，ABS10，KOL11]的工作，基于子空间枚举技术。
The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle Transversal. In this work, we consider the following model of instances: starting with a set of vertices $V$, a set $S \subseteq V$ of $k$ vertices is chosen and an arbitrary $d$-regular bipartite graph is added on it; edges between pairs of vertices in $S \times (V \setminus S)$ and $(V \setminus S) \times (V \setminus S)$ are added with probability $p$. Since for $d=0$, the problem reduces to recovering a planted independent set, we don't expect efficient algorithms for $k=o(\sqrt{n})$. This problem is a generalization of the planted balanced biclique problem where the bipartite graph induced on $S$ is a complete bipartite graph; [Lev18] gave an algorithm for recovering $S$ in this problem when $k=Ω(\sqrt{n})$. Our main result is an efficient algorithm that recovers (w.h.p.) the planted bipartite graph when $k=Ω_p(\sqrt{n \log n})$ for a large range of parameters. Our results also hold for a natural semi-random model of instances, which involve the presence of a monotone adversary. Our proof shows that a natural SDP relaxation for the problem is integral by constructing an appropriate solution to it's dual formulation. Our main technical contribution is a new approach for constructing the dual solution where we calibrate the eigenvectors of the adjacency matrix to be the eigenvectors of the dual matrix. We believe that this approach may have applications to other recovery problems in semi-random models as well. When $k=Ω(\sqrt{n})$, we give an algorithm for recovering $S$ whose running time is exponential in the number of small eigenvalues in graph induced on $S$; this algorithm is based on subspace enumeration techniques due to the works of [KT07,ABS10,Kol11].
