Falk Hüffner: Automated Generation of Branch&Reduce Algorithms for Graph Modification Problems
We present a framework for the automated generation of exact
branch&reduce algorithms for NP-hard problems. The purpose of our
approach is two-fold: rapid development and improved upper bounds.
Many branch&reduce algorithms for various problems in the
literature are based on complicated case distinctions. Our approach
may lead to a much simpler process of developing and analyzing these
algorithms. Moreover, using the sheer computing power of machines it
can also provide improved upper bounds on search tree sizes (i.e.,
faster exact algorithms) in comparison with previously developed
“hand-made” search trees.
A central example in this work is given with the NP-complete Cluster Editing problem, which
asks for the minimum number of edge additions and deletions in a graph
to create a cluster graph (i.e., a graph which is a disjoint union of
cliques). For Cluster
Editing, a hand-made search tree is known with
O(2.27k) worst-case size, which is improved
to O(1.92k) due to our new method. Herein,
k denotes the number of edge modifications allowed.