Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

DOI10.1016/j.dam.2011.07.009zbMath1237.05146OpenAlexW2012700732MaRDI QIDQ411835

Vangelis Th. Paschos, Nicolas Bourgeois, Bruno Escoffier

Publication date: 30 April 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/9038

zbMATH Keywords

approximation algorithmsmaximum independent setexponential time algorithmsminimum vertex cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, A review on algorithms for maximum clique problems, Time-approximation trade-offs for inapproximable problems, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, An exponential time 2-approximation algorithm for bandwidth, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Exponential approximation schemata for some network design problems, Parameterized approximation via fidelity preserving transformations, Super-polynomial approximation branching algorithms, Improved (In-)Approximability Bounds for d-Scattered Set, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Sparsification and subexponential approximation, When polynomial approximation meets exact computation, Approximating MAX SAT by moderately exponential and parameterized algorithms, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, On the max min vertex cover problem, When polynomial approximation meets exact computation, Algorithms for dominating clique problems, New tools and connections for exponential-time approximation, On subexponential and FPT-time inapproximability, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Exponential-time approximation of weighted set cover
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Which problems have strongly exponential complexity?
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex Cover: Further Observations and Further Improvements
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Proof verification and the hardness of approximation problems
• On Approximate Solutions for Combinatorial Optimization Problems
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Parameterized Approximability
• Parameterized Approximation Problems
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Bottom-Up Method and Fast Algorithms for max independent set
• Confronting hardness using a hybrid approach
• Vertex packings: Structural properties and algorithms
• On approximation properties of the Independent set problem for degree 3 graphs
• STACS 2005
• Automata, Languages and Programming