On the complexity of approximating the independent set problem
From MaRDI portal
It is shown that for some positive constant \(c\) it is not feasible to approximate the independent set (for graphs of \(n\) vertices) within a factor of \(n^ c\), provided maximum 2-satisfiability does not have a randomized polynomial time approximation scheme. Reductions preserving the quality of approximations are also studied and complete problems are exhibited.
Recommendations
- On the complexity of approximating the independent set problem (extended abstract)
- On approximation properties of the independent set problem for low degree graphs
- On approximation properties of the Independent set problem for degree 3 graphs
- On the hardness of approximating minimization problems
- Approximating the minimum maximal independence number
Cites work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Approximation algorithms for combinatorial problems
- scientific article; zbMATH DE number 3887060 (Why is no real title available?)
- scientific article; zbMATH DE number 3871363 (Why is no real title available?)
- scientific article; zbMATH DE number 3670509 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3557234 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- Non deterministic polynomial optimization problems and their approximations
- Structure preserving reductions among convex optimization problems
- The Complexity of Some Problems on Subsequences and Supersequences
- Toward a unified approach for the classification of NP-complete optimization problems
Cited in
(83)- On approximating four covering and packing problems
- On the hardness of approximating max-satisfy
- Optimization, approximation, and complexity classes
- Approximating maximum independent sets by excluding subgraphs
- Zero knowledge and the chromatic number
- On approximation properties of the independent set problem for low degree graphs
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
- Approximating the independence number via the -function
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Ramsey theory and integrality gap for the independent set problem
- Derandomized graph products
- Independence number and the complexity of families of sets
- The complexity of irredundant sets parameterized by size
- Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
- Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
- On the analysis of optimization problems in arc-dependent networks
- Faster exponential-time algorithms for approximately counting independent sets
- On the complexity of the independent set problem in triangle graphs
- On constructing an optimal consensus clustering from multiple clusterings
- On approximating the \(d\)-girth of a graph
- The resolution complexity of independent sets and vertex covers in random graphs
- Inapproximability results for the lateral gene transfer problem
- Resource bounds and subproblem independence
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Analyzing read-once cutting plane proofs in Horn systems
- The biclique k-clustering problem in bipartite graphs and its application in bioinformatics
- Finding independent sets in unions of perfect graphs
- A fine-grained analysis of a simple independent set algorithm
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- A natural family of optimization problems with arbitrarily small approximation thresholds
- Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Computational complexity of the graph approximation problem
- On the complexity of the minimum independent set partition problem
- Expander graphs and their applications
- Some independence results in complexity theory†
- A note on anti-coordination and social interactions
- Kernel bounds for path and cycle problems
- scientific article; zbMATH DE number 1223713 (Why is no real title available?)
- A survey on the structure of approximation classes
- The approximation of maximum subgraph problems
- Polynomially bounded minimization problems which are hard to approximate
- The Complexity of Problems in P Given Correlated Instances
- scientific article; zbMATH DE number 751135 (Why is no real title available?)
- scientific article; zbMATH DE number 845765 (Why is no real title available?)
- scientific article; zbMATH DE number 1405687 (Why is no real title available?)
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- On independent sets, 2-to-2 games, and Grassmann graphs
- On minrank and the Lovász theta-function
- Approximating maximum independent sets by excluding subgraphs
- On approximation properties of the Independent set problem for degree 3 graphs
- Approximation of Constraint Satisfaction via local search
- On approximating the longest path in a graph
- On the complexity of approximating the independent set problem (extended abstract)
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Constructing concrete hard instances of the maximum independent set problem
- Non-approximability results for optimization problems on bounded degree instances
- The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
- Expanding operators for the independent set problem
- Paired approximation problems and incompatible inapproximabilities
- Approximability of the independent feedback vertex set problem for bipartite graphs
- A generalization of maximal independent sets
- Hardness and methods to solve CLIQUE
- Structure in approximation classes
- On the complexity of distance-\(d\) independent set reconfiguration
- Reachability in choice networks
- Unit read-once refutations for systems of difference constraints
- A differentiable approach to the maximum independent set problem using dataless neural networks
- The combinatorial game \textsc{Nofil} played on Steiner triple systems
- Constructive -- non-constructive approximation and maximum independent set problem
- Arc-dependent networks: theoretical insights and a computational study
- Orthonormal representations, vector chromatic number, and extension complexity
- On complexity classes of envy-free pricing problems: a short survey
- Approximate solution of NP optimization problems
- Approximation algorithm for DNF under distributions with limited independence
- Complexities of efficient solutions of rectilinear polygon cover problems
- On approximating the longest path in a graph
- Approximating the minimum maximal independence number
- Nearly orthogonal sets over finite fields
- Optimal length cutting plane refutations of integer programs
- On approximating the minimum independent dominating set
- On approximation problems related to the independent set and vertex cover problems
This page was built for publication: On the complexity of approximating the independent set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1184733)
