New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs

2009/04/17 by Mingyu Xiao, Xiao, Mingyu
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.0904.2712

openalex publication_date 2009/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an O^*(1.0919ⁿ)-time algorithm for finding a maximum independent set in an n-vertex graph with degree bounded by 3, which improves the previously known algorithm of running time O^*(1.0977ⁿ) by Bourgeois, Escoffier and Paschos [IWPEC 2008]. We also present an O^*(1.1923^k)-time algorithm to decide if a graph with degree bounded by 3 has a vertex cover of size k, which improves the previously known algorithm of running time O^*(1.1939^k) by Chen, Kanj and Xia [ISAAC 2003]. Two new branching techniques, branching on a bottle and branching on a 4-cycle, are introduced, which help us to design simple and fast algorithms for the maximum independent set and minimum vertex cover problems and avoid tedious branching rules.

Related

• A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
• Targeted Branching for the Maximum Independent Set Problem
• Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
• Extension of vertex cover and independent set in some classes of graphs and generalizations
• A faster algorithm for Vertex Cover parameterized by solution size