Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis

DOI10.3390/a11010010zbMath1461.68160arXiv1705.03581OpenAlexW2613308084MaRDI QIDQ2633244

Pasin Manurangsi

Publication date: 8 May 2019

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hardness of approximationsmall set expansion hypothesismaximum edge bicliquedensest at-least-\( k\)-subgraphmaximum balanced bicliqueminimum \( k\)-cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

The Bipartite QUBO ⋮ On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ New approximations and hardness results for submodular partitioning problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• Noise stability of functions with low influences: invariance and optimality
• On the complexity of approximating the independent set problem
• Expected complexity of graph partitioning problems
• The maximum edge biclique problem is NP-complete
• Which problems have strongly exponential complexity?
• Complexity of finding dense subgraphs
• Derandomized graph products
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Proof verification and the hardness of approximation problems
• Relations between average case complexity and approximation complexity
• On the power of unique 2-prover 1-round games
• Finding Dense Subgraphs with Size Bounds
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• On Finding Dense Subgraphs
• Probabilistic checking of proofs
• Large Cliques Elude the Metropolis Process
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• Approximation Algorithms for Label Cover and The Log-Density Threshold
• ETH Hardness for Densest-k-Subgraph with Perfect Completeness
• Bi-Covering: Covering Edges with Two Small Subsets of Vertices
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Analysis of Boolean Functions
• Optimal Long Code Test with One Free Bit
• Analytical approach to parallel repetition
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Segmentation problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The NP-completeness column: An ongoing guide
• The dense \(k\)-subgraph problem
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts

This page was built for publication: Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis