Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
From MaRDI portal
Publication:897878
DOI10.1016/J.TCS.2015.09.023zbMATH Open1331.68281arXiv1411.2680OpenAlexW2513955757MaRDI QIDQ897878FDOQ897878
Authors: Takuya Akiba, Yoichi Iwata 
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1411.2680
Recommendations
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Improved upper bounds for vertex cover
- Branching and Treewidth Based Exact Algorithms
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Analytical and experimental comparison of six algorithms for the vertex cover problem
Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A measure \& conquer approach for the analysis of exact algorithms
- Finding odd cycle transversals.
- Linear-time FPT algorithms via network flow
- Half-integrality, LP-branching and FPT algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Vertex packings: Structural properties and algorithms
- Improved upper bounds for vertex cover
- Fast algorithms for max independent set
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Algorithm Engineering for Optimal Graph Bipartization
- Title not available (Why is that?)
- Faster parameterized algorithms using linear programming
- A simple and faster branch-and-bound algorithm for finding a maximum clique
- A faster algorithm for dominating set analyzed by the potential method
- A fine-grained analysis of a simple independent set algorithm
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Exact Algorithms for Maximum Independent Set
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
Cited In (26)
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
- Algorithms and Data Structures
- Data Reduction for Maximum Matching on Real-World Graphs
- A probabilistic algorithm for vertex cover
- Title not available (Why is that?)
- An Updated Experimental Evaluation of Graph Bipartization Methods
- Maximum independent sets and supervised learning
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- A polynomial-space exact algorithm for TSP in degree-6 graphs
- A refined algorithm for maximum independent set in degree-4 graphs
- Scale reduction techniques for computing maximum induced bicliques
- Differentiable discrete optimization using dataless neural networks
- Search-space reduction via essential vertices
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Reinforcement learning for combinatorial optimization: a survey
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- On the power of simple reductions for the maximum independent set problem
- Title not available (Why is that?)
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Research trends in combinatorial optimization
- A differentiable approach to the maximum independent set problem using dataless neural networks
- Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
- Why is maximum clique often easy in practice?
- Solving vertex cover in polynomial time on hyperbolic random graphs
Uses Software
This page was built for publication: Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897878)
