Abstract
The problem of computing the vertex expansion of a graph is an NPhard problem. The current best worstcase approximation guarantees for computing the vertex expansion of a graph are a O(sqrt{log n})approximation algorithm due to Feige et al. [Uriel Feige et al., 2008], and O(sqrt{OPT log d}) bound in graphs having vertex degrees at most d due to Louis et al. [Louis et al., 2013].
We study a natural semirandom model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bicriteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph.
In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semirandom graphs with planted sparse edge cuts. To the best of our knowledge, our model of semirandom graphs with planted sparse vertex cuts has not been studied before.
BibTeX  Entry
@InProceedings{louis_et_al:LIPIcs:2018:9105,
author = {Anand Louis and Rakesh Venkat},
title = {{Semirandom Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {101:1101:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9105},
URN = {urn:nbn:de:0030drops91057},
doi = {10.4230/LIPIcs.ICALP.2018.101},
annote = {Keywords: SemiRandom models, Vertex Expansion, Approximation Algorithms, Beyond Worst Case Analysis}
}
Keywords: 

SemiRandom models, Vertex Expansion, Approximation Algorithms, Beyond Worst Case Analysis 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 