Planted Models for k-way Edge and Vertex Expansion

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 2- partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k > 2. For a k-partition S1, . . . , Sk of the vertex set of a graph G = (V, E), the k-way edge expansion (resp. vertex expansion) of {S1, . . . , Sk} is defined as maxi∈[k] Φ(Si), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min {S1,...,Sk}∈Pk max i∈[k] Φ(Si), where Pk is the set of all balanced k-partitions of V (i.e each part of a k-partition in Pk should have cardinality |V | /k), and Φ(S) denotes the edge expansion (resp. vertex expansion) of S ⊂ V . We study a natural planted model for graphs where the vertex set of a graph has a k-partition S1, . . . , Sk such that the graph induced on each Si has large expansion, but each Si has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing