Source-linked AI summary
Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
Takuya Akiba, Yoichi Iwata
TL;DR
Exact branching research offers strong theoretical algorithms, but their practical value has been less established. This paper builds and tests a branch-and-reduce Vertex Cover algorithm, finding it practical and competitive on several instance types.
Problem
The paper addresses the gap between theoretically fastest exact branching algorithms and empirically fastest methods for benchmark instances.
Method
The authors design a Vertex Cover branch-and-reduce algorithm combining theoretical rules, lower bounds, and new packing branching and reduction rules.
Results
The algorithm is practical and competitive with CPLEX branch-and-cut and MCS branch-and-bound for several instance types.
Takeaways & Limitations
The experiments indicate that developing theoretical branching and reduction techniques can also lead to empirical efficiency.
Takeaways & Limitations
CPLEX results were sensitive to simplex feasibility tolerance, indicating numerical precision issues in the comparison.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper examines the gap between theoretically fastest and empirically fastest exact branching algorithms, then evaluates whether branch-and-reduce techniques are practical for Vertex Cover.
- Motivation: Branch-and-reduce methods have the best known time complexity for several important problems, while practice often uses branch-and-bound or branch-and-cut methods.The theoretical methods use many branching and reduction rules, whereas empirical methods commonly rely on problem-specific or LP-based lower bounds.
- Approach: The study designs a Vertex Cover algorithm combining theoretical branching, reduction, and lower-bound techniques with new packing rules.Vertex Cover is chosen because it has been extensively studied both theoretically and empirically.
- Evaluation: The algorithm is compared experimentally with CPLEX branch-and-cut and MCS branch-and-bound on varied instances.The comparison targets two state-of-the-art empirical approaches.
- Theoretical context: Exact exponential algorithms improve worst-case complexity through branching and reductions, including a recurrence yielding O*(1.6181^n) in a simple example.The example illustrates how connected-component reduction and degree-based branching improve the basic O*(2^n) algorithm.
- Theoretical context: The paper builds on theoretical algorithms for general and sparse graphs, including an O*(1.2210^n)-time result and rules from Fomin et al. and Xiao and Nagamochi.The cited work motivates the rules incorporated into the practical algorithm.
- Parameterized context: For parameterized Vertex Cover, the algorithm uses an LP-based reduction and lower bound, while experiments also examine instances reduced from Odd Cycle Transversal.The paper reports that solving Odd Cycle Transversal through Vertex Cover strongly outperforms its state-of-the-art algorithm.
2 Preliminaries
The preliminaries define graph neighborhoods, induced subgraphs, and Vertex Cover, including the requirement that every edge has at least one endpoint in the cover.
- Graph notation: For an undirected graph G=(V,E), vertex degree is denoted d(v), and N(v) and N[v] denote open and closed neighborhoods.The closed neighborhood is N[v]=N(v)∪{v}.
- Graph notation: N(S) denotes the neighbors of a vertex subset outside the subset, while N[S] adds the subset itself.The notation is extended to vertices at distance d through N^d(v).
- Vertex Cover: A vertex cover is a subset C containing at least one endpoint of every edge, and Vertex Cover asks for a minimum such subset.The set of all minimum vertex covers is denoted vc(G).
3 Algorithm Overview
The algorithm recursively reduces the graph and packing constraints, prunes infeasible states, separates disconnected components, and branches until the graph is empty.
- Complexity: After computing the LP lower bound, the algorithm has a stated O(4^k m) running time.The passage presents this bound as a footnote associated with the algorithm.
- Algorithm interface: The procedure receives a graph, packing constraints, a current solution size, and an upper bound.These are the inputs listed for Algorithm 1.
- Recursive procedure: Each recursive call first applies reduction rules and returns the upper bound when the packing constraints are unsatisfied.This places reduction and constraint-based pruning before further branching.
- Packing constraints: Packing constraints are auxiliary pruning and reduction devices rather than constraints used to strengthen the LP relaxation.They are created by the paper’s new branching and reduction rules.
4 Branching Rules
The branching rules select structurally useful vertices and use mirrors, satellites, and packing constraints to guide branches, reductions, and pruning.
- Branch selection: The implementation selects a maximum-degree branching vertex, breaking ties by minimizing the number of edges among its neighbors.Random and minimum-degree selection strategies are evaluated as alternatives.
- Mirror branching: A mirror of v is a distance-two vertex u for which N(v)\N(u) induces a clique or is empty.When mirrors exist, the implementation branches by including M[v] or discarding v while including N(v).
- Satellite branching: A satellite of v is a distance-two vertex u associated with a neighbor w whose external neighborhood is exactly {u}.The paper describes a satellite branching rule and replaces it in the implementation with a more powerful rule introduced later.
- Packing branching: Packing constraints prune a search node when a right-hand side becomes negative and can trigger reductions when it reaches zero.The constraints encode cases where alternative covers of the same or smaller size can be obtained.
- Packing branching: The total size of packing constraints is at most linear in graph size, so explicitly maintaining them does not seriously affect computation time.At most one constraint is created per vertex, and each constraint is bounded by the corresponding degree.
5 Reduction Rules
The algorithm combines reduction rules from exact exponential and FPT research, including LP-based, sparse-graph, and newly developed packing reductions.
- Reductions from Exponential Algorithms: Four reductions from Fomin et al. include components, degree-1, dominance, and degree-2 folding.The degree-1 rule is computationally cheaper despite being contained in the components and dominance rules; degree-2 folding replaces a local structure with a new vertex.
- Reductions from FPT Algorithms: The LP reduction fixes zero-valued vertices outside the cover and one-valued vertices inside it using persistency.The implementation uses an extreme half-integral optimum whose half-integral part is minimal, so other LP optima cannot enable further deletions.
- Implementation: Maximum matchings are maintained incrementally rather than recomputed from scratch after reductions or branchings.The current matching is augmented through residual-graph paths to restore maximality.
- Reductions from Exponential Algorithms for Sparse Graphs: Sparse-graph reductions include alternatives, unconfined vertices, twins, and related graph transformations.Alternatives generalize several special cases, while unconfined vertices can be included in some minimum vertex cover and twins permit graph simplification.
- Packing Reductions: Packing constraints support pruning and reductions, with a zero right-hand side forbidding selected vertices and enabling deletion when no internal edge exists.Positive-right-hand-side rules can force vertices into the cover or replace a vertex while preserving cover size; constraints must be checked after reversing affected graph modifications.
6 Lower Bounds
The algorithm uses several efficiently computable lower bounds for Vertex Cover and takes their maximum in its main implementation.
- Clique Cover: A clique cover gives the lower bound |V|−k, equivalently the sum of |C_i|−1 over k disjoint cliques.The implementation constructs a clique cover greedily in linear time.
- Comparison: The clique-cover bound is also used by MCS, whose more sophisticated computation does not scale for large graphs.This motivates the simpler greedy computation used here.
- LP Lower Bound: The LP optimum is a lower bound for the minimum vertex cover, and after LP reduction the remaining graph has value |V|/2.This lower bound is used in parameterized algorithms based on the gap between LP and integer optima.
- Cycle Cover: A cycle cover also supplies a lower bound, and it is never worse than the LP optimum after LP-based reduction.A perfect matching yields a cycle cover in O(|V|) time, and splitting certain even cycles into odd cycles can improve the bound.
7 Experiments
The experiments evaluate branch-and-reduce (B&R) against CPLEX and MCS across sparse networks, DIMACS graphs, and Odd Cycle Transversal instances, then test branching, reduction, and lower-bound choices. B&R is competitive across several instance types, with branching and reduction rules having the clearest practical effects.
- Experimental setup: The evaluation covers real sparse networks, DIMACS instances, and graphs derived from Odd Cycle Transversal, using B&R, CPLEX, and MCS as primary comparators.Hüffner’s direct Odd Cycle Transversal algorithm is additionally included for those instances.
- Algorithm comparison: B&R and CPLEX clearly outperform MCS on real sparse networks, while B&R is generally comparable with CPLEX except on road networks.B&R solves several instances CPLEX misses within the time limit and is orders of magnitude faster on some others, whereas CPLEX alone solves a few web graphs within the limit.
- Algorithm comparison: MCS generally works better on DIMACS instances, while B&R and CPLEX remain comparable and solve different subsets of instances that the other cannot solve.MCS is tailored to DIMACS graphs and uses greedy coloring for lower bounds without reductions.
- Algorithm comparison: B&R, CPLEX, and MCS strongly outperform Hüffner’s algorithm on Odd Cycle Transversal instances.The comparison includes real bioinformatics instances representing the Minimum Site Removal problem.
- Branching strategies: Maximum-degree branching (B2) is significantly better than minimum-degree and random branching, while minimum-degree branching outperforms random branching.The paper attributes the latter result to mirror branching occurring more often on small-degree vertices.
- Reduction rules and lower bounds: Reduction rules substantially shrink the search space and increase the number of problems solved within the time limit, whereas lower-bound differences have a smaller effect.Without reductions, R0 cannot solve any problems; among lower-bound variants, L4 has the smallest search space, and L3 consistently improves on L2.
8 Conclusion
The study finds that theoretical branching and reduction techniques have practical as well as theoretical importance, yielding empirical efficiency.
- Experimental results indicate that developing branching and reduction techniques leads to empirical efficiency in addition to theoretical importance.
A Parameterized Complexity of Vertex Cover above Lower Bounds
The paper examines whether strong clique-cover and cycle-cover lower bounds make Vertex Cover tractable under parameterization, contrasting them with LP-based results.
- Clique cover and cycle cover can provide better lower bounds than LP relaxation for Vertex Cover.
- Even when clique-cover and cycle-cover lower bounds are close to the optimum, the corresponding parameterized problems can remain difficult.
A.1 Vertex Cover above Clique Cover
Vertex Cover above Clique Cover asks whether a vertex cover can exceed the clique-cover lower bound by only a parameter k; the paper proves this problem parameterized NP-hard.
- The problem seeks a vertex cover of size at most |V| − |C| + k, where |V| − |C| is the lower bound obtained from a given clique cover.
- The paper proves that Vertex Cover above Clique Cover is parameterized NP-hard.
- The proof reduces 3-SAT to the problem using variable edges, clause triangles, and connections between clause vertices and corresponding literals.
- The reduction establishes satisfiability exactly when the constructed graph has a vertex cover of size n + 2m.
A.2 Vertex Cover above Cycle Cover
The paper defines Vertex Cover above Cycle Cover analogously and proves it parameterized NP-hard by reusing the clique-cover reduction.
- Vertex Cover above Cycle Cover uses a cycle cover and parameter k to bound the permitted vertex-cover size above its cycle-cover lower bound.
- The paper proves that Vertex Cover above Cycle Cover is parameterized NP-hard.
- The clique cover from the first proof is also a cycle cover because every clique has size two or three.
- For clique sizes two or three, the lower-bound contribution |C| − 1 is identical under clique-cover and cycle-cover interpretations, enabling the same proof.