Louis, Anand and Venkat, Rakesh
(2019)
Planted Models for kway Edge and Vertex Expansion.
arXiv.org.
Full text not available from this repository.
(
Request a copy)
Abstract
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 kpartition S1, . . . , Sk of the vertex set of a graph G = (V, E), the kway edge
expansion (resp. vertex expansion) of {S1, . . . , Sk} is defined as maxi∈[k] Φ(Si), and the balanced
kway 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 kpartitions of V (i.e each part of a kpartition 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 kpartition
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 bicriteria approximation algorithms
for computing t
[error in script]
Actions (login required)

View Item 