# Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover

arXiv: https://arxiv.org/abs/1411.2680 · HTML: https://mlsanity.com/paper/1411.2680/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2014.

## Built on by (most cited first, 8 of 8)

- [Augment with Care: Contrastive Learning for Combinatorial Problems](https://mlsanity.com/paper/2202.08396/) (2022)
- [A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks](https://mlsanity.com/paper/2203.08209/) (2022)
- [A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem](https://mlsanity.com/paper/2307.16815/) (2023)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Mining Large Independent Sets on Massive Graphs](https://mlsanity.com/paper/2208.07777/) (2022)
- [Improved Exact and Heuristic Algorithms for Maximum Weight Clique](https://mlsanity.com/paper/2302.00458/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study](https://mlsanity.com/paper/2609.02804/) (2026)

## Abstract (arXiv)

We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous important problems. On the other hand, in practice, state-of-the-art methods are based on different approaches, and the empirical efficiency of such theoretical algorithms have seldom been investigated probably because they are seemingly inefficient because of the plethora of complex reduction rules. In this paper, we design a branch-and-reduce algorithm for the vertex cover problem using the techniques developed for theoretical algorithms and compare its practical performance with other state-of-the-art empirical methods. The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms.