Planted Models for $k$-way Edge and Vertex Expansion

Anand Louis, Rakesh Venkat

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a…