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

DOI10.3390/A11010010zbMATH Open1461.68160arXiv1705.03581OpenAlexW2613308084MaRDI QIDQ2633244FDOQ2633244

Authors: Pasin Manurangsi 

Publication date: 8 May 2019

Published in: Algorithms (Search for Journal in Brave)

Abstract: The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose edge expansion is almost zero and one in which all small subsets of vertices have expansion almost one. In this work, we prove inapproximability results for the following graph problems based on this hypothesis: - Maximum Edge Biclique (MEB): given a bipartite graph $G$, find a complete bipartite subgraph of $G$ with maximum number of edges. - Maximum Balanced Biclique (MBB): given a bipartite graph $G$, find a balanced complete bipartite subgraph of $G$ with maximum number of vertices. - Minimum $k$-Cut: given a weighted graph $G$, find a set of edges with minimum total weight whose removal partitions $G$ into $k$ connected components. - Densest At-Least-$k$-Subgraph (DAL$k$S): given a weighted graph $G$, find a set $S$ of at least $k$ vertices such that the induced subgraph on $S$ has maximum density (the ratio between the total weight of edges and the number of vertices). We show that, assuming SSEH and NP $subseteq$ BPP, no polynomial time algorithm gives $n^{1-varepsilon}$-approximation for MEB or MBB for every constant $varepsilon>0$. Moreover, assuming SSEH, we show that it is NP-hard to approximate Minimum $k$-Cut and DAL$k$S to within $(2-varepsilon)$ factor of the optimum for every constant $varepsilon>0$. The ratios in our results are essentially tight since trivial algorithms give $n$-approximation to both MEB and MBB and efficient $2$-approximation algorithms are known for Minimum $k$-Cut [SV95] and DAL$k$S [And07, KS09]. Our first result is proved by combining a technique developed by Raghavendra et al. [RST12] to avoid locality of gadget reductions with a generalization of Bansal and Khot's long code test [BK09] whereas our second result is shown via elementary reductions.

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

Recommendations

• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• Hardness of bipartite expansion
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• On Set Expansion Problems and the Small Set Expansion Conjecture

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)

Cites Work

• Relations between average case complexity and approximation complexity
• Title not available (Why is that?)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Which problems have strongly exponential complexity?
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Approximation algorithms for maximization problems arising in graph partitioning
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Proof verification and the hardness of approximation problems
• On Finding Dense Subgraphs
• Probabilistic checking of proofs
• Analysis of Boolean Functions
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The dense \(k\)-subgraph problem
• Complexity of finding dense subgraphs
• Tree packing and approximating \(k\)-cuts
• Derandomized graph products
• On the power of unique 2-prover 1-round games
• Noise stability of functions with low influences: invariance and optimality
• On the complexity of approximating the independent set problem
• Large Cliques Elude the Metropolis Process
• Analytical approach to parallel repetition
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Graph expansion and the unique games conjecture
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Finding k Cuts within Twice the Optimal
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
• The maximum edge biclique problem is NP-complete
• Segmentation problems
• Title not available (Why is that?)
• Expected complexity of graph partitioning problems
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Finding Dense Subgraphs with Size Bounds
• Optimal Long Code Test with One Free Bit
• The NP-completeness column: An ongoing guide
• Title not available (Why is that?)
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Title not available (Why is that?)
• An FPT algorithm beating 2-approximation for \(k\)-cut
• A birthday repetition theorem and complexity of approximating dense CSPs
• Approximation algorithms for label cover and the log-density threshold
• Bi-covering: covering edges with two small subsets of vertices
• Hardness of vertex deletion and project scheduling
• ETH hardness for densest-\(k\)-subgraph with perfect completeness

Cited In (20)

• New approximations and hardness results for submodular partitioning problems
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Hypergraph \(k\)-cut in randomized polynomial time
• The bipartite QUBO
• On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
• Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
• Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
• On a connection between small set expansions and modularity clustering
• Mathematics of computation through the lens of linear equations and lattices
• Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
• Hardness of bipartite expansion
• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Approximating submodular \(k\)-partition via principal partition sequence
• A parameterized approximation scheme for min \(k\)-cut
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis

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

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