The complexity status of problems related to sparsest cuts

DOI10.1007/978-3-642-19222-7_14MaRDI QIDQ3000501zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Viresh Patel, Hajo Broersma, Artem Pyatkin

Publication date 19 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19222-7_14

zbMATH Keywords

bounded treewidthNP-hardnesssparsest cutMSSCdensest cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of finding uniform sparsest cuts in various graph classes
• Sparsest cuts and bottlenecks in graphs
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• On the hardness of approximating Multicut and Sparsest-Cut

Cites work

• scientific article; zbMATH DE number 49455 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating sparsest cut in graphs of bounded treewidth
• Clustering large graphs via the singular value decomposition
• Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
• Expander flows, geometric embeddings and graph partitioning
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Linear time algorithms for finding sparsest cuts in various graph classes
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• NP-hardness of Euclidean sum-of-squares clustering
• Some simplified NP-complete graph problems
• Sparsest cuts and bottlenecks in graphs
• Sparsest cuts and concurrent flows in product graphs.
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time

Cited in

(10)

• On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• The Complexity of Partial Function Extension for Coverage Functions
• Increasing the minimum degree of a graph by contractions
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• On the hardness of approximating Multicut and Sparsest-Cut
• Linear time algorithms for finding sparsest cuts in various graph classes
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• The complexity of finding uniform sparsest cuts in various graph classes
• Multi-way sparsest cut problem on trees with a control on the number of parts and outliers

This page was built for publication: The complexity status of problems related to sparsest cuts

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