Improved Complexity Bound of Vertex Cover for Low degree Graph

2010/10/14 by Weiya Yue, Yue, Weiya, John Franco +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1010.2833

openalex publication_date 2010/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we use a new method to decrease the parameterized complexity bound for finding the minimum vertex cover of connected max-degree-3 undirected graphs. The key operation of this method is reduction of the size of a particular subset of edges which we introduce in this paper and is called as "real-cycle" subset. Using "real-cycle" reductions alone we compute a complexity bound O(1.15855^k) where k is size of the optimal vertex cover. Combined with other techniques, the complexity bound can be further improved to be O(1.1504^k). This is currently the best complexity bound.

Related

• A modified greedy algorithm to improve bounds for the vertex cover number
• Weighted vertex cover on graphs with maximum degree 3
• A Proposed Algorithm for Minimum Vertex Cover Problem and its Testing
• A faster algorithm for Vertex Cover parameterized by solution size
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4