Approximation algorithms for finding maximum induced expanders

DOI10.1137/1.9781611974782.75MaRDI QIDQ4575817zbMATH OpenOpenAlexFDO

Authors Shayan Oveis Gharan, Alireza Rezaei

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02786

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We initiate the study of approximating the largest induced expander in a given graph $G$. Given a $Delta$-regular graph $G$ with $n$ vertices, the goal is to find the set with the largest induced expansion of size at least $deltacdotn$. We design a bi-criteria approximation algorithm for this problem; if the optimum has induced spectral expansion $lambda$ our algorithm returns a $fraclambdalo{g}^{2}deltaexp(Delta/lambda)$-(spectral) expander of size at least $deltan$ (up to constants). Our proof introduces and employs a novel semidefinite programming relaxation for the largest induced expander problem. We expect to see further applications of our SDP relaxation in graph partitioning problems. In particular, because of the close connection to the small set expansion problem, one may be able to obtain new insights into the unique games problem.

Recommendations

• Graph expansion and the unique games conjecture
• Expander flows, geometric embeddings and graph partitioning
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• Subexponential algorithms for unique games and related problems
• Expander flows, geometric embeddings and graph partitioning

Cited in

(1)

• Finding large expanders in graphs: from topological minors to induced subgraphs

This page was built for publication: Approximation algorithms for finding maximum induced expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575817)