Seminář G²OAT: Generating faster algorithms for d-Path Vertex Cover

Abstrakt

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 $d$, the $d$-Path Vertex Cover problem ($d$-PVC) is as follows: Given an undirected graph and an integer $k$, find a subset of at most $k$ vertices of the graph, such that their deletion results in a graph not containing a path on $d$ 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 $3\le d\le 8$, e.g., we show that $5$-PVC can be solved in $O({2.7}^k\cdot n^{O(1)})$ time.

Další události