On set expansion problems and the small set expansion conjecture

DOI10.1016/J.DAM.2015.05.028zbMATH Open1319.05105OpenAlexW620970122WikidataQ123002417 ScholiaQ123002417MaRDI QIDQ494429FDOQ494429

Authors: Rajiv Gandhi, Guy Kortsarz 

Publication date: 1 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.05.028

Recommendations

• On Set Expansion Problems and the Small Set Expansion Conjecture
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• Graph expansion and the unique games conjecture
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion

zbMATH Keywords

edge coveringdense graphssmall set expansion

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• \(k\)-edge subgraph problems
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Title not available (Why is that?)
• Primal-Dual Schema for Capacitated Covering Problems
• On Finding Dense Subgraphs
• Title not available (Why is that?)
• The dense \(k\)-subgraph problem
• Graph expansion and the unique games conjecture
• Finding Dense Subgraphs with Size Bounds
• On the \(k\)-edge-incident subgraph problem and its variants
• On Set Expansion Problems and the Small Set Expansion Conjecture
• Density functions subject to a co-matroid constraint

Cited In (4)

• On Set Expansion Problems and the Small Set Expansion Conjecture
• Small Generating Sets and DLPC Problem
• The small set vertex expansion problem
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications

This page was built for publication: On set expansion problems and the small set expansion conjecture

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