3 papers
cs.DS2026
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 where each vertex from has a weight and the first player…
cs.CC2026
PLS-complete problems with lexicographic cost functions: Max--SAT and Abelian Permutation Orbit Minimization
Dominik Scheder, Johannes Tantow
How hard is it to find a local optimum? If we are given a graph and want to find a locally maximal cut--meaning that the number of edges in the cut can't be improved by moving a si…
cs.CC2025
PLS-completeness of string permutations
Dominik Scheder, Johannes Tantow
Bitstrings can be permuted via permutations and compared via the lexicographic order. In this paper we study the complexity of finding a minimum of a bitstring via given permutatio…