Solving Stackelberg Vertex Cover on trees using split and join

Dominik Scheder, Johannes Tantow

The Stackelberg Vertex Cover problem is a bilevel optimization problem with two players on a graph G = ($F\cup P$, E) where each vertex from F has a weight and the first player se…