New algorithms solve Stackelberg Vertex Cover on trees with split and join

A new arXiv preprint by Dominik Scheder and Johannes Tantow tackles the computationally challenging Stackelberg Vertex Cover problem on trees. This bilevel optimization has a leader setting prices on a subset of vertices (P), then a follower picks a minimum vertex cover; the leader's revenue comes from the price of P-vertices in that cover. Previously known to be NP-complete on bipartite graphs but linear on paths, the authors now extend solvability to wider tree classes with three novel algorithms.

First, they give a pseudo-polynomial algorithm for general trees with integer weights – fixed-parameter tractable (FPT) when the maximum weight is the parameter. Second, a strongly polynomial algorithm works for trees where the least common ancestor of any two P-vertices is also in P (a condition satisfied by paths). Third, an FPT algorithm uses the maximum number of P-vertices reachable from a single F-vertex without using other P-vertices as the parameter. All algorithms rely on a split-and-join lemma derived from LP duality and the integrality of vertex cover LP on bipartite graphs, plus a new commitment concept to ensure sub-instance agreement on vertices. The authors also prove that Stackelberg Vertex Cover with commitments is weakly NP-complete.