Abstract
Many algorithms that solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error-prone, and often, the resulting algorithm may be difficult to implement in practice.
In this work, we aim to automate a part of this process and focus on the simplicity of the resulting implementation.
We showcase our approach to the following problem. For a constant , the -Path Vertex Cover problem (-PVC) is as follows: Given an undirected graph and an integer , find a subset of at most vertices of the graph, such that their deletion results in a graph not containing a path on vertices as a subgraph. We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for , e.g., we show that -PVC can be solved in time.