11 papers
A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach
Many problems are known to be solvable in subexponential parameterized time when the input graph is planar. The bidimensionality framework of Demaine, Fomin, Hajiaghay, and Thiliko…
Line Cover and Related Problems
Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4
We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of points in the plane can be covered using lines. Line Cover is known to be NP-hard,…
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…
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…
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…
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) -vertex graph alo…