{"id":"arxiv/2606.17604","url":"https://arxiv.org/abs/2606.17604","tags":["cs.DS","math.PR","math.ST"],"score":0,"title":"Spectral recovery of a planted triangle-dense subgraph","domain":"cs.DS","source":"arxiv","authors":["Sam van der Poel","Cheng Mao","Benjamin McKenna"],"reviews":0,"subject":"cs.DS","summary":"Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erdős-Rényi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}