Graph Modification Problems and Automated Search Tree Generation

tree algorithms for NP-hard problems. The purpose of our approach is
two-fold: rapid development and improved upper bounds.

Many search tree 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
solving algorithms) in comparison with previously developed
``hand-made'' search trees. The generated search tree algorithms work
by expanding a ``window view'' of the problem with local information,
and then branch according to a precalculated rule for the resulting
window.

A central example 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.27^k)$ worst-case size, which is improved to
$O(1.92^k)$ due to our new method. (Herein, $k$ denotes the number of
edge modifications allowed.)