2 papers
cs.DS2024
The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
Matthias Bentert, Fedor V. Fomin, Fanny Hauser +1
In Two-Sets Cut-Uncut, we are given an undirected graph and two terminal sets and . The task is to find a minimum cut in (if there is any) separating f…
cs.DS2024
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Matthias Bentert, Klaus Heeger, Tomohiro Koana
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal i…