Improved upper bounds for vertex cover

This paper presents an O(1.2738^k+kn)-time polynomial-space algorithm for Vertex Cover improving the previous O(1.286^k+kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. Several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. The algorithm also improves the O(1.2745^kk^4+kn)-time exponential-space upper bound for the problem by Chandran and Grandoni.

• Publication year

  2010

• Venue

  Theoretical Computer Science

• Publication date

  2010-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2010.06.026
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Open problems around exact algorithms

  2008cited by this paper
• Crown reductions for the Minimum Weighted Vertex Cover problem

  2008influential reference
• Refined memorization for vertex cover

  2005cited by this paper
• Measure and Conquer: Domination - A Case Study

  2005cited by this paper
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations

  2005cited by this paper
• Refined Memorisation for Vertex Cover

  2004influential reference
• Exact algorithms for finding k disjoint triangles in an arbitrary graph ∗

  2004cited by this paper
• Looking at the stars

  2004cited by this paper
• Greedy Localization, Iterative Compression, Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover

  2004cited by this paper
• Packing Edge Disjoint Triangles: A Parameterized View

  2004cited by this paper
• Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps

  2004cited by this paper
• Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

  2003cited by this paper
• Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPT

  2003cited by this paper
• Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms - The Case of k-Internal Spanning Tree

  2003cited by this paper
• Solving large FPT problems on coarse-grained parallel machines

  2003cited by this paper
• On the existence of subexponential parameterized algorithms

  2003cited by this paper
• A general method to speed up fixed-parameter-tractable algorithms

  2000cited by this paper
• Reports in Informatics

  2000cited by this paper
• Improvement on vertex cover for low-degree graphs

  2000cited by this paper
• On Efficient Fixed Parameter Algorithms for WEIGHTED VERTEX COVER

  2000cited by this paper
• Upper Bounds for Vertex Cover Further Improved

  1999cited by this paper
• An improved fixed parameter tractable algorithm for vertex cover

  1999cited by this paper
• Vertex Cover: Further Observations and Further Improvements

  1999cited by this paper
• Which problems have strongly exponential complexity?

  1998cited by this paper
• An Improved Fixed-Parameter Algorithm for Vertex Cover

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Cliques, Coloring, and Satisfiability

  1996cited by this paper
• Nondeterminism Within P

  1993cited by this paper
• Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy

  1992cited by this paper
• Algorithms for Maximum Independent Sets

  1986cited by this paper
• Pseudo-Boolean functions and stability of graphs

  1984cited by this paper
• A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982influential reference
• Vertex packings: Structural properties and algorithms

  1975cited by this paper
• : BLOW-UPS

  year unknowncited by this paper

• Techniques in parameterized approximation

  2026cites this paper
• Temporal Dominating Set and Temporal Vertex Cover Under the Lense of Degree Restrictions

  2025cites this paper
• Solving Partial Dominating Set and Related Problems Using Twin-Width

  2025cites this paper
• Efficient Algorithms for Approximate k-Radius Coverage Query on Large-Scale Road Networks

  2025cites this paper
• Broadcasting under Structural Restrictions

  2025cites this paper
• Faster winner determination algorithms for (Colored) Arc Kayles

  2025cites this paper
• Optimizing Minimum Vertex Cover Solving via a GCN-assisted Heuristic Algorithm

  2025cites this paper
• Structural Parameterization of Cluster Deletion

  2025cites this paper
• An efficient local search algorithm for the maximum k-vertex cover problem

  2025cites this paper
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

  2025cites this paper
• Faster Vertex Cover Algorithms on GPUs With Component-Aware Parallel Branching

  2025cites this paper
• Vertex cover number in diverse graph architectures

  2025cites this paper
• An Attention-Based Method for the Minimum Vertex Cover Problem on Complex Networks

  2024cites this paper
• Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k

  2024cites this paper
• Parameterized Vertex Integrity Revisited

  2024cites this paper
• Losing Treewidth In The Presence Of Weights

  2024cites this paper
• Computational complexity of normalizing constants for the product of determinantal point processes

  2024cites this paper
• Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs

  2024cites this paper
• Solving Co-Path/Cycle Packing Faster than 3k

  2024cites this paper
• Grouped domination parameterized by vertex cover, twin cover, and beyond

  2024cites this paper
• Forest Covers and Bounded Forest Covers

  2024cites this paper
• Parameterized Algorithms for Minimum Sum Vertex Cover

  2024cites this paper
• Parameterized Spanning Tree Congestion

  2024cites this paper
• Subexponential Parameterized Algorithms for Hitting Subgraphs

  2024cites this paper
• Parameterized Quantum Query Algorithms for Graph Problems

  2024cites this paper
• Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks

  2024cites this paper
• Core Stability in Additively Separable Hedonic Games of Low Treewidth

  2024cites this paper
• On the parameterized complexity of non-hereditary relaxations of clique

  2024cites this paper
• Approximation Algorithm and FPT Algorithm for Connected-k-Subgraph Cover on Minor-Free Graphs

  2024cites this paper
• A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees

  2024cites this paper
• Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

  2023cites this paper
• Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs

  2023cites this paper
• Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

  2023cites this paper
• Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover

  2023cites this paper
• Parameterized Complexity of Simultaneous Planarity

  2023cites this paper
• Defensive Alliances in Signed Networks

  2023cites this paper
• On the Parameterized Complexity of Relaxations of Clique

  2023cites this paper
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs

  2023cites this paper
• The Parametrized Complexity of the Segment Number

  2023cites this paper
• Relay Pursuit for Multirobot Target Tracking on Tile Graphs

  2023cites this paper
• Optimal Seat Arrangement: What Are the Hard and Easy Cases?

  2023cites this paper
• Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs

  2023cites this paper
• Parameterized Analysis of the Cops and Robber Problem

  2023cites this paper
• How to Make Knockout Tournaments More Popular?

  2023cites this paper
• Parameterized Complexity of Broadcasting in Graphs

  2023cites this paper
• Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

  2023cites this paper
• 5-Approximation for $\mathcal{H}$-Treewidth Essentially as Fast as $\mathcal{H}$-Deletion Parameterized by Solution Size

  2023cites this paper
• Perceptions of Beauty in Security Ceremonies

  2022cites this paper
• k-apices of Minor-closed Graph Classes. II. Parameterized Algorithms

  2022influential citation
• Search-Space Reduction via Essential Vertices

  2022cites this paper
• An Efficient Algorithm for Maximum Trajectory Coverage Query With Approximation Guarantee

  2022cites this paper
• Solving larger maximum clique problems using parallel quantum annealing

  2022cites this paper
• Parameterizing Path Partitions

  2022influential citation
• Efficient Feedback and Partial Credit Grading for Proof Blocks Problems

  2022cites this paper
• Using hierarchies to efficiently combine evidence with Dempster's rule of combination

  2022cites this paper
• On the Complexity of the Storyplan Problem

  2022cites this paper
• Correlating Theory and Practice in Finding Clubs and Plexes

  2022cites this paper
• A Multivariate Complexity Analysis of Qualitative Reasoning Problems

  2022cites this paper
• Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited

  2022cites this paper
• Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time

  2022cites this paper
• On the External Validity of Average-case Analyses of Graph Algorithms

  2022cites this paper
• Winner Determination Algorithms for Graph Games with Matching Structures

  2022cites this paper
• There and Back Again: On Applying Data Reduction Rules by Undoing Others

  2022cites this paper
• A novel rough set-based approach for minimum vertex cover of hypergraphs

  2022cites this paper
• Parameterized Approximations via Randomized

  2022cites this paper
• On book thickness parameterized by the vertex cover number

  2022cites this paper
• Approximation and inapproximability results on computing optimal repairs

  2022cites this paper
• A Refined Branching Algorithm for the Maximum Satisfiability Problem

  2022cites this paper
• Reducing the Vertex Cover Number via Edge Contractions

  2022cites this paper
• Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

  2022cites this paper
• ShadowAuth: Backward-Compatible Automatic CAN Authentication for Legacy ECUs

  2022cites this paper
• A Survey on the k-Path Vertex Cover Problem

  2022cites this paper
• On the d-Claw Vertex Deletion Problem

  2022cites this paper
• Atmospheric Propagation Modelling for Terrestrial Radio Frequency Communication Links in a Tropical Wet and Dry Savanna Climate

  2022cites this paper
• Reordering a Tree According to an Order on Its Leaves

  2022cites this paper
• Efficient Partial Credit Grading of Proof Blocks Problems

  2022cites this paper
• A faster algorithm for Vertex Cover parameterized by solution size

  2022influential citation
• Parallel Vertex Cover Algorithms on GPUs

  2022cites this paper
• Solving Larger Optimization Problems Using Parallel Quantum Annealing

  2022cites this paper
• Deletion to Scattered Graph Classes II - Improved FPT Algorithms for Deletion to Pairs of Graph Classes

  2022influential citation
• An Algorithmic Framework for Locally Constrained Homomorphisms

  2022cites this paper
• A local search method based on edge age strategy for minimum vertex cover problem in massive graphs

  2021cites this paper
• On Kernels for d-Path Vertex Cover

  2021influential citation
• On Extended Formulations For Parameterized Steiner Trees

  2021cites this paper
• On the Upward Book Thickness Problem: Combinatorial and Complexity Results

  2021cites this paper
• Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set

  2021cites this paper
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes

  2021cites this paper
• Fixed-Parameter Sensitivity Oracles

  2021cites this paper
• Clique, Independent Set, and Vertex Cover

  2021cites this paper
• Parameterized Algorithms for the Steiner Tree Problem on a Directed Hypercube

  2021cites this paper
• Preventing Small $\mathbf{(s,t)}$-Cuts by Protecting Edges

  2021cites this paper
• Chapter 10 Approximation algorithms

  2021cites this paper
• Worst-case analysis of clique MIPs

  2021cites this paper
• Parameterized Algorithms for Linear Layouts of Graphs with Respect to the Vertex Cover Number

  2021cites this paper
• Generating faster algorithms for d-Path Vertex Cover

  2021cites this paper
• Possibilistic Data Cleaning

  2021cites this paper
• Journal of Computer and System Sciences Your to know your colleagues: Triadic closure with edge colors ✩

  2021cites this paper
• Fixed-Parameter Tractability

  2021cites this paper
• Augmented intuition: a bridge between theory and practice

  2021cites this paper
• Compactors for parameterized counting problems

  2021cites this paper