2026-10-02T08:23:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26068 2026-09-23T23:59:30Z ddc:004 open_access

Semirandom Planted Bipartite Subgraphs Louis, Anand Vora, Kirtan Semirandom Models Spectral Algorithms Planted Subgraphs Random Graphs Approximate Recovery Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anand Louis and Kirtan Vora 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.32 urn:nbn:de:0030-drops-260681 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode