Clique is hard to approximate within \(n^{1-\epsilon}\)

From MaRDI portal

Publication:1588908

Jump to:navigation, search

DOI10.1007/BF02392825zbMath0989.68060WikidataQ56210419 ScholiaQ56210419MaRDI QIDQ1588908

Johan T. Håstad

Publication date: 6 December 2000

Published in: Acta Mathematica (Search for Journal in Brave)

zbMATH Keywords

CLIQUE problem Max-Clique

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Maximum cliques in graphs with small intersection number and random intersection graphs, Independent sets in semi-random hypergraphs, Shrinking maxima, decreasing costs: new online packing and covering problems, An options-based solution to the sequential auction problem, Isolation concepts for efficiently enumerating dense subgraphs, Approximation and hardness results for the max \(k\)-uncut problem, A lower bound on the independence number of a graph in terms of degrees and local clique sizes, Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, Optimal approximation algorithms for maximum distance-bounded subgraph problems, A note on unique games, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, Notes on complexity of packing coloring, Geometric representation of graphs in low dimension using axis parallel boxes, On the computational complexity of the virtual network embedding problem, Coloring immersion-free graphs, Common information and unique disjointness, A copositive formulation for the stability number of infinite graphs, Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Longest common subsequence problem for unoriented and cyclic strings, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, The complexity of egalitarian mechanisms for linear programming games, Some recent progress and applications in graph minor theory, Strong lift-and-project cutting planes for the stable set problem, A note on anti-coordination and social interactions, Self-improved gaps almost everywhere for the agnostic approximation of monomials, Moderately exponential approximation for makespan minimization on related machines, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Computing the partition function for graph homomorphisms with multiplicities, On the \(b\)-continuity of the lexicographic product of graphs, Independence in connected graphs, Complexity of finding maximum regular induced subgraphs with prescribed degree, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, An exact algorithm for the maximum probabilistic clique problem, Staying safe and visible via message sharing in online social networks, Partial multicovering and the \(d\)-consecutive ones property, Geometric rounding: A dependent randomized rounding scheme, Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane, On maximizing the throughput of multiprocessor tasks., Welfare maximization with friends-of-friends network externalities, The advice complexity of a class of hard online problems, Copositive optimization -- recent developments and applications, Domination analysis of combinatorial optimization problems., Computing large independent sets in a single round, On the complexity of reconfiguration problems, Constant-degree graph expansions that preserve treewidth, Graph problems arising from parameter identification of discrete dynamical systems, The many facets of upper domination, Approximability of constrained LCS, Cliques enumeration and tree-like resolution proofs, On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs, Approximation algorithms for maximum independent set of pseudo-disks, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Cutting planes cannot approximate some integer programs, On the inapproximability of maximum intersection problems, A survey on the structure of approximation classes, The complexity of König subgraph problems and above-guarantee vertex cover, Differential approximation results for the Steiner tree problem, On the complexity of optimization over the standard simplex, Distributed discovery of large near-cliques, 2-approximation algorithm for finding a clique with minimum weight of vertices and edges, Distributed approximation of \(k\)-service assignment, Approximability results for the maximum and minimum maximal induced matching problems, Approximability of the subset sum reconfiguration problem, Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, On a posterior evaluation of a simple greedy method for set packing, Complete partitions of graphs, Computing the partition function for graph homomorphisms, Hardness of computing clique number and chromatic number for Cayley graphs, Statistical analysis of financial networks, Solving connected dominating set faster than \(2^n\), Finding quasi core with simulated stacked neural networks, Maximum regular induced subgraphs in \(2P_3\)-free graphs, Complexity issues for the sandwich homogeneous set problem, Minimum entropy combinatorial optimization problems, A simpler characterization of a spectral lower bound on the clique number, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, A lower bound on independence in terms of degrees, On the complexity of fixed parameter clique and dominating set, Inapproximability results for equations over infinite groups, A simple algorithm for 4-coloring 3-colorable planar graphs, Project scheduling with irregular costs: complexity, approximability, and algorithms, Interpolating between bounds on the independence number, Hyperbolic set covering problems with competing ground-set elements, On linear and semidefinite programming relaxations for hypergraph matching, Exponential-time approximation of weighted set cover, Approximating the maximum vertex/edge weighted clique using local search, Lower bounds for treewidth of product graphs, Consistent sets of secondary structures in proteins, Approximating the maximum clique minor and some subgraph homeomorphism problems, Zero knowledge and the chromatic number, Large independent sets in random regular graphs, Isolation concepts for clique enumeration: comparison and computational experiments, Priority algorithms for graph optimization problems, An effective local search for the maximum clique problem, Interactive and probabilistic proof-checking, On the hardness of approximating max-satisfy, BOB: Improved winner determination in combinatorial auctions and generalizations, The complexity of estimating min-entropy, Partial digest is hard to solve for erroneous input data, The consensus string problem and the complexity of comparing hidden Markov models., Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching, Towards optimal lower bounds for clique and chromatic number., An SDP-based approach for computing the stability number of a graph, On the accuracy of uniform polyhedral approximations of the copositive cone, Bayesian agency: linear versus tractable contracts, On the approximability of clique and related maximization problems, Phased local search for the maximum clique problem, A review on algorithms for maximum clique problems, Mechanism design for policy routing, Online crowdsourced truck delivery using historical information, On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs, Approximation schemes for a class of subset selection problems, Matroid representation of clique complexes, Least and most colored bases, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Mechanisms for information elicitation, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, Improved approximation algorithms for the spanning star forest problem, Stochastic budget optimization in internet advertising, Collision-free routing problem with restricted L-path, On approximability of optimization problems related to red/blue-split graphs, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, The stable set problem: clique and nodal inequalities revisited, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms, Generating binary partial Hadamard matrices, On the 2-Club Polytope of Graphs, Approximation and Hardness Results for the Max k-Uncut Problem, Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, Independent sets in Line of Sight networks, A note on approximating the \(b\)-chromatic number, Donation center location problem, PASS approximation: a framework for analyzing and designing heuristics, Finding Large Independent Sets in Line of Sight Networks, A Lower Bound of the cd-Chromatic Number and Its Complexity, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Competitive router scheduling with structured data, Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes, Sum of squares basis pursuit with linear and second order cone programming, Scheduling split intervals with non-uniform demands, On the minimum monochromatic or multicolored subgraph partition problems, A simple simulated annealing algorithm for the maximum clique problem, Parallel computations and committee constructions, Computing inductive vertex orderings, Dense subgraphs in random graphs, A New Approach to the Stable Set Problem Based on Ellipsoids, Generalizing the induced matching by edge capacity constraints, Improving ADMMs for solving doubly nonnegative programs through dual factorization, Relaxing the strong triadic closure problem for edge strength inference, Optimization over structured subsets of positive semidefinite matrices via column generation, On the Lovász theta function and some variants, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Competitive algorithms for multistage online scheduling, Parameterized approximability of maximizing the spread of influence in networks, Separable standard quadratic optimization problems, New potential functions for greedy independence and coloring, Independent set of intersection graphs of convex objects in 2D, Exploring the relationship between max-cut and stable set relaxations, Approximation of knapsack problems with conflict and forcing graphs, Clique-detection models in computational biochemistry and genomics, Conversion of coloring algorithms into maximum weight independent set algorithms, Extractors from Reed-Muller codes, Inapproximability and approximability of maximal tree routing and coloring, Mining market data: a network approach, The complexity of detecting fixed-density clusters, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, On extracting maximum stable sets in perfect graphs using Lovász's theta function, A branch-and-cut algorithm for the edge interdiction clique problem, Extended formulations for vertex cover, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Approximation in (Poly-) logarithmic space, Dynamic programming optimization in line of sight networks, Approximating graph-constrained max-cut, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Flexible allocation on related machines with assignment restrictions, Truthful approximation mechanisms for restricted combinatorial auctions, (In)approximability of maximum minimal FVS, Upper Domination: Complexity and Approximation, CP decomposition and weighted clique problem, Strengthened clique-family inequalities for the stable set polytope, Structurally parameterized \(d\)-scattered set, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, The Maximum Matrix Contraction Problem, On the Maximum Uniquely Restricted Matching for Bipartite Graphs, Worst-case analysis of clique MIPs, The complexity of finding harmless individuals in social networks, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Dynamic node packing, Advice complexity of maximum independent set in sparse and bipartite graphs, Finding disjoint paths in networks with star shared risk link groups, Incentive compatible mulit-unit combinatorial auctions: a primal dual approach, Vertex coloring edge-weighted digraphs, A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem., The \(k\)-separator problem: polyhedra, complexity and approximation results, Differential approximation for optimal satisfiability and related problems, Packing under convex quadratic constraints, Inferring local transition functions of discrete dynamical systems from observations of system behavior, Packing Under Convex Quadratic Constraints, Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems, Analysis of MILP Techniques for the Pooling Problem, Independent Sets in Restricted Line of Sight Networks, On approximating MIS over B1-VPG graphs*, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Combinatorial Auctions with Conflict-Based Externalities, On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs, Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems, Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes, Independent sets in asteroidal triple-free graphs, Estimating the Size of Branch-and-Bound Trees, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, Inductive graph invariants and approximation algorithms, Inapproximability of Maximum Weighted Edge Biclique and Its Applications, Geometric Packing under Nonuniform Constraints, Pseudorandom sets in Grassmann graph have near-perfect expansion, Improved (In-)Approximability Bounds for d-Scattered Set, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, A spectral algorithm for finding maximum cliques in dense random intersection graphs, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Elliptic polytopes and invariant norms of linear operators, Unnamed Item, Spectrum Bidding in Wireless Networks and Related, CliSAT: a new exact algorithm for hard maximum clique problems, Scheduling with machine conflicts, Advice complexity of adaptive priority algorithms, Expander graphs and their applications, Mathematics of computation through the lens of linear equations and lattices, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs, On Regularity Lemmas and their Algorithmic Applications, Introduction to Testing Graph Properties, Problems on One Way Road Networks, The Approximability of Assortment Optimization Under Ranking Preferences, Parallel Repetition of Two-Prover One-Round Games: An Exposition, APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS, The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, Why Is Maximum Clique Often Easy in Practice?, A guide to conic optimisation and its applications, Near Approximation of Maximum Weight Matching through Efficient Weight Reduction, Recoverable Values for Independent Sets, A new branch-and-bound algorithm for standard quadratic programming problems, In)approximability of Maximum Minimal FVS, Minimum Entropy Combinatorial Optimization Problems, Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Approximating Independent Set and Coloring in Random Uniform Hypergraphs, Unnamed Item, Unnamed Item, Mining relevant information on the Web: a clique-based approach, A priori optimization for the probabilistic maximum independent set problem, Algorithm for optimal winner determination in combinatorial auctions, Inapproximability of finding maximum hidden sets on polygons and terrains, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Robust Independence Systems, Finding a Dense-Core in Jellyfish Graphs, Global equilibrium search applied to the unconstrained binary quadratic optimization problem, GreedyMAX-type Algorithms for the Maximum Independent Set Problem, Overflow management with self-eliminations, Testing for Dense Subsets in a Graph via the Partition Function, \(\ell_1\)-sparsity approximation bounds for packing integer programs, Overflow management with self-eliminations, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Short Locally Testable Codes and Proofs, Introduction to Testing Graph Properties, DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, On the Approximability of Some Haplotyping Problems, Approximation in (Poly-) Logarithmic Space, A Retrospective on Genomic Preprocessing for Comparative Genomics, Counting Weighted Independent Sets beyond the Permanent, Enumerating Isolated Cliques in Synthetic and Financial Networks, Unnamed Item, Leafy spanning arborescences in DAGs, On the Hardness of Energy Minimisation for Crystal Structure Prediction*, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1588908&oldid=13886134"