Semirandom Planted Bipartite Subgraphs

There have been many recent works studying planted subgraphs problems. The semirandom planted bipartite subgraph problem is defined as follows. Starting with a vertex set V, an arbitrary subset S ⊂ V of size k is chosen, then an arbitrary bipartite graph is added on S. After this between each pair of vertices in S × (V ⧵ S) an edge is added independently with probability p, then an arbitrary graph is added on V⧵ S. The analogous semirandom planted clique problem, where S forms a clique, has been studied starting with the work of Fiege and Kilian [Uriel Feige and Joe Kilian, 2001]; recent work by [Blasiok et al., 2024; Venkatesan Guruswami and Hsin-Po Wang, 2025] gave an algorithm for this problem when k = Ω(√{n log n}). We give an algorithm for semirandom planted bipartite subgraph problem when k = Ω(√{n log n}) and the two color classes are roughly balanced. Our algorithms are essentially the same as the elegant greedy algorithm of [Blasiok et al., 2024]. We generalize their idea to our setting. Handling the arbitrary nature of the bipartite graph requires some new technical ideas and is our main technical contribution.