On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems

DOI10.1016/J.DAM.2024.04.014MaRDI QIDQ6559388zbMATH OpenFDO

Authors Ramin Javadi

Publication date 21 June 2024

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.04.014

zbMATH Keywords

parameterized complexitysmall-set expansionsparsest cuttreewidthvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• The complexity status of problems related to sparsest cuts
• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• The complexity of finding uniform sparsest cuts in various graph classes
• The small set vertex expansion problem

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Bin packing with fixed number of bins revisited
• Clustering and outlier detection using isoperimetric number of trees
• Expander flows, geometric embeddings and graph partitioning
• Graph theory with applications
• Grundy distinguishes treewidth from pathwidth
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• On the complexity of isoperimetric problems on trees
• Parameterized algorithms
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The complexity of finding uniform sparsest cuts in various graph classes
• Tree-depth, subgraph coloring and homomorphism bounds
• Which problems have strongly exponential complexity?

This page was built for publication: On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems

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