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

DOI10.3390/A11010010MaRDI QIDQ2633244zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

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.

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

Cites work

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

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)