Improved Analysis of Highest-Degree Branching for Feedback Vertex Set

2019/05/29 by Yoichi Iwata, Iwata, Yoichi, Yusuke Kobayashi +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Branching (polymer chemistry) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Degree (music) #Discrete mathematics #FOS: Computer and information sciences #Feedback vertex set #Graph #Heuristic #Mathematical optimization #Mathematics #Physics #Pruning #Set (abstract data type) #Vertex (graph theory) #cs.DS

paper · pdf · doi:10.48550/arxiv.1905.12233

arxiv created 2019/05/29 · openalex publication_date 2019/05/29 · arxiv updated 2019/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk.

Citations

• A measure & conquer approach for the analysis of exact algorithms

Cited by

• The Parameter Report: An Orientation Guide for Data-Driven Parameterization

Related

• A Naive Algorithm for Feedback Vertex Set
• Faster deterministic Feedback Vertex Set
• Detecting Feedback Vertex Sets of Size k in O^⋆(2.7^k) Time
• A note on the complexity of Feedback Vertex Set parameterized by mim-width
• Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set