Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
From MaRDI portal
Publication:5757457
DOI10.1137/S0097539705447037zbMath1127.68035MaRDI QIDQ5757457
Publication date: 7 September 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (67)
Hardness and approximation of traffic grooming ⋮ Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal ⋮ The Densest $k$-Subhypergraph Problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ Complexity and approximability of the happy set problem ⋮ Finding connected \(k\)-subgraphs with high density ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ The vertex attack tolerance of complex networks ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ On approximating string selection problems with outliers ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ Vertex downgrading to minimize connectivity ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ Additive stabilizers for unstable graphs ⋮ Hardness results for approximating the bandwidth ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Auditing for core stability in participatory budgeting ⋮ Phase transitions in semidefinite relaxations ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Improved approximation algorithms for label cover problems ⋮ A Dynamic Programming Heuristic for the Quadratic Knapsack Problem ⋮ Unnamed Item ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ Derandomized parallel repetition via structured PCPs ⋮ Unnamed Item ⋮ A dynamic edge covering and scheduling problem: complexity results and approximation algorithms ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ On set expansion problems and the small set expansion conjecture ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ In search of the densest subgraph ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Graph classes and approximability of the happy set problem ⋮ Unnamed Item ⋮ Balanced coloring of bipartite graphs ⋮ The ordered covering problem ⋮ Graph Stabilization: A Survey ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ The densest subgraph problem with a convex/concave size function ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ Unnamed Item ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ An Improved Branch-and-Bound Method for Maximum Monomial Agreement ⋮ On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation ⋮ On the complexity of fair house allocation ⋮ Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs ⋮ Unnamed Item ⋮ Nearly Optimal NP-Hardness of Unique Coverage ⋮ Unnamed Item ⋮ On solving the densestk-subgraph problem on large graphs ⋮ PTAS for densest \(k\)-subgraph in interval graphs
This page was built for publication: Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
