On the complexity of approximating the independent set problem

DOI10.1016/0890-5401(92)90056-LMaRDI QIDQ1184733zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Georg Schnitger

Publication date 28 June 1992

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90056-l

zbMATH Keywords

independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

• 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?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Approximation algorithms for combinatorial problems
• 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

(79)

• Arc-dependent networks: theoretical insights and a computational study
• Orthonormal representations, vector chromatic number, and extension complexity
• Some independence results in complexity theory^†
• A differentiable approach to the maximum independent set problem using dataless neural networks
• Constructing concrete hard instances of the maximum independent set problem
• Reachability in choice networks
• Structure in approximation classes
• Approximation of Constraint Satisfaction via local search
• Unit read-once refutations for systems of difference constraints
• scientific article; zbMATH DE number 845765 (Why is no real title available?)
• Constructive -- non-constructive approximation and maximum independent set problem
• On minrank and the Lovász theta-function
• On complexity classes of envy-free pricing problems: a short survey
• The combinatorial game \textsc{Nofil} played on Steiner triple systems
• Optimization, approximation, and complexity classes
• Approximating the minimum maximal independence number
• Computational complexity of the graph approximation problem
• Resource bounds and subproblem independence
• Faster exponential-time algorithms for approximately counting independent sets
• On approximation properties of the Independent set problem for degree 3 graphs
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
• The approximation of maximum subgraph problems
• Kernel bounds for path and cycle problems
• Approximating maximum independent sets by excluding subgraphs
• On constructing an optimal consensus clustering from multiple clusterings
• A generalization of maximal independent sets
• Zero knowledge and the chromatic number
• Approximating maximum independent sets by excluding subgraphs
• On independent sets, 2-to-2 games, and Grassmann graphs
• Exponential Time Complexity of Weighted Counting of Independent Sets
• The resolution complexity of independent sets and vertex covers in random graphs
• Finding independent sets in unions of perfect graphs
• scientific article; zbMATH DE number 1405687 (Why is no real title available?)
• Independence number and the complexity of families of sets
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
• Approximation algorithm for DNF under distributions with limited independence
• On approximation properties of the independent set problem for low degree graphs
• Approximating the independence number via the \(\vartheta\)-function
• On approximating four covering and packing problems
• On the hardness of approximating max-satisfy
• Ramsey theory and integrality gap for the independent set problem
• On approximating the minimum independent dominating set
• On the analysis of optimization problems in arc-dependent networks
• Paired approximation problems and incompatible inapproximabilities
• On approximating the \(d\)-girth of a graph
• Derandomized graph products
• A note on anti-coordination and social interactions
• On the complexity of the minimum independent set partition problem
• Expander graphs and their applications
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• On approximating the longest path in a graph
• Approximate solution of NP optimization problems
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• Non-approximability results for optimization problems on bounded degree instances
• The Complexity of Problems in P Given Correlated Instances
• On approximation problems related to the independent set and vertex cover problems
• Polynomially bounded minimization problems which are hard to approximate
• The complexity of irredundant sets parameterized by size
• The biclique \(k\)-clustering problem in bipartite graphs and its application in bioinformatics
• A fine-grained analysis of a simple independent set algorithm
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Complexities of efficient solutions of rectilinear polygon cover problems
• Analyzing read-once cutting plane proofs in Horn systems
• On the complexity of the independent set problem in triangle graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• Expanding operators for the independent set problem
• A natural family of optimization problems with arbitrarily small approximation thresholds
• Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
• Hardness and methods to solve CLIQUE
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Approximability of the independent feedback vertex set problem for bipartite graphs
• On the complexity of approximating the independent set problem (extended abstract)
• On approximating the longest path in a graph
• A survey on the structure of approximation classes
• Inapproximability results for the lateral gene transfer problem

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)