Planted Models for \(k\)-way Edge and Vertex Expansion

• Published in: arXiv.org 2019-10
• Main Authors: Anand, Louis, Venkat, Rakesh
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity theory; Partitioning; Partitions
• ISSN: 2331-8422

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 \geq 2\). For a \(k\)-partition \(S_1, \ldots, S_k\) of the vertex set of a graph \(G = (V,E)\), the \(k\)-way edge expansion (resp. vertex expansion) of \(\{S_1, \ldots, S_k\}\) is defined as \(\max_{i \in [k]} \Phi(S_i)\), and the balanced \(k\)-way edge expansion (resp. vertex expansion) of \(G\) is defined as \[ \min_{ \{S_1, \ldots, S_k\} \in \mathcal{P}_k} \max_{i \in [k]} \Phi(S_i) \, , \] where \(\mathcal{P}_k\) is the set of all balanced \(k\)-partitions of \(V\) (i.e each part of a \(k\)-partition in \(\mathcal{P}_k\) should have cardinality \(|V|/k\)), and \(\Phi(S)\) denotes the edge expansion (resp. vertex expansion) of \(S \subset V\). We study a natural planted model for graphs where the vertex set of a graph has a \(k\)-partition \(S_1, \ldots, S_k\) such that the graph induced on each \(S_i\) has large expansion, but each \(S_i\) has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced \(k\)-way edge expansion (resp. vertex expansion) of instances in this planted model.