Solving Stackelberg Vertex Cover on trees using split and join
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
The authors study a tricky problem where two players interact on a graph: one sets prices on certain vertices and the other picks a smallest set of vertices covering all edges to buy. The goal is for the first player to maximize their earnings. They present three new methods to solve this problem on special kinds of tree graphs, each with different assumptions about weights and graph structure. Their approach uses a key idea from linear programming to break the problem into smaller parts, introducing a concept called commitments to handle tricky cases. They also show that even with commitments, the problem remains hard in a certain sense.
Authors
Dominik Scheder, Johannes Tantow
Abstract
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 selects a price for each vertex in $P$. Afterwards, the second player finds a minimum vertex cover $X$ and the first player receives the set price for each vertex from $X \cap P$. The goal is to maximize the revenue of the first player. This problem was recently shown to be NP-complete for bipartite graphs while being solvable in linear time on paths. We present three new algorithms for solving Stackelberg Vertex Cover on certain kinds of trees: (1) a pseudo-polynomial algorithm working on general trees when all weights are integer, i.e., it is FPT with the maximum weight as a parameter; (2) a strongly polynomial algorithm for trees having the property that the least common ancestor of any two vertices from $P$ is again in $P$ (this case includes paths); and (3) an FPT-algorithm for trees, where the parameter is the maximum number $P$-vertices $v_i$ that an $F$-vertex $u$ can reach while using no other $P$-vertices. These algorithms are based on a lemma that allows us to split instances at a vertex $u$ into multiple sub-instances, which follows from LP duality and integrality of the vertex cover LP on bipartite graphs. The lemma requires that the minimum vertex covers of the sub-instances agree on $u$ (either all include $u$ or all don't). For this we introduce the concept of commitments. Finally, we show that the Stackelberg Vertex Cover problem with commitments is weakly NP-complete.