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.