Preventing Small Global Cuts by Protecting Edges
Here, the most natural parameters such as the budgets d and a of the players, the vertex cover number and treewidth of the input graph, and combinations of these parameters are considered, showing that the encoding of the costs and weights of the edges has a considerable influence on the problem complexity.