3 papers
cs.DS2025
H-Planarity and Parametric Extensions: when Modulators Act Globally
Fedor V. Fomin, Petr A. Golovach, Laure Morelle +1
We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend…
cs.DS2025
Fault-Tolerant Matroid Bases
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid M and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of eleme…
cs.DS2025
When does FTP become FPT?
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers…