On set expansion problems and the small set expansion conjecture

DOI10.1016/J.DAM.2015.05.028MaRDI QIDQ494429zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

Cited in

(4)

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

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)