Matthias Bentert
YOU?
Author Swipe
View article: Packing Short Cycles
Packing Short Cycles Open
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths …
View article: The Directed Disjoint Paths Problem with Congestion
The Directed Disjoint Paths Problem with Congestion Open
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-known result, we show that the directed disjoint paths proble…
View article: Fault-Tolerant Matroid Bases
Fault-Tolerant Matroid Bases Open
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 elements such that, even after the removal of any k elements, th…
View article: Overlapping Biclustering
Overlapping Biclustering Open
We study the problem of transforming bipartite graphs into bicluster graphs. Abu-Khzam, Isenmann, and Merchad [IWOCA '25] introduced two variants of this problem. In both problems, the goal is to transform a bipartite graph into a bicluste…
View article: Cluster Editing with Vertex Splitting
Cluster Editing with Vertex Splitting Open
View article: Planar Network Diversion
Planar Network Diversion Open
Network Diversion is a graph problem that has been extensively studied in both the network-analysis and operations-research communities as a measure of how robust a network is against adversarial disruption. This problem is especially well…
View article: Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems Open
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest kn…
View article: Correlation Clustering with Vertex Splitting
Correlation Clustering with Vertex Splitting Open
View article: The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
The Parameterized Complexity Landscape of Two-Sets Cut-Uncut Open
View article: Packing Short Cycles
Packing Short Cycles Open
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths …
View article: A Space-Efficient Algebraic Approach to Robotic Motion Planning
A Space-Efficient Algebraic Approach to Robotic Motion Planning Open
We consider efficient route planning for robots in applications such as infrastructure inspection and automated surgical imaging. These tasks can be modeled via the combinatorial problem Graph Inspection. The best known algorithms for this…
View article: The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
The Parameterized Complexity Landscape of Two-Sets Cut-Uncut Open
In Two-Sets Cut-Uncut, we are given an undirected graph $G=(V,E)$ and two terminal sets $S$ and $T$. The task is to find a minimum cut $C$ in $G$ (if there is any) separating $S$ from $T$ under the following ``uncut'' condition. In the gra…
View article: Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
Leveraging Fixed-Parameter Tractability for Robot Inspection Planning Open
Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and e…
View article: The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths Open
We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where each color appears (roughly) equally often in the solution.…
View article: Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication Open
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 in terms of connectivity. Vertex integrity is the smallest n…
View article: Correlation Clustering with Vertex Splitting
Correlation Clustering with Vertex Splitting Open
We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both prob…
View article: Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model Open
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either \emph{safe} or \emph{unsafe} and we assume that failures only affect unsafe edges. In Unweighted F…
View article: Fair Short Paths in Vertex-Colored Graphs
Fair Short Paths in Vertex-Colored Graphs Open
The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. For the setting where each vertex is assigned to a…
View article: Two-sets cut-uncut on planar graphs
Two-sets cut-uncut on planar graphs Open
We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such th…
View article: A multivariate complexity analysis of the material consumption scheduling problem
A multivariate complexity analysis of the material consumption scheduling problem Open
The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980’s. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources—each job has individual r…
View article: Polynomial-time data reduction for weighted problems beyond additive goal functions
Polynomial-time data reduction for weighted problems beyond additive goal functions Open
View article: Parameterized Complexity of Diameter
Parameterized Complexity of Diameter Open
Diameter —the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $$O(n^{1.99})$$ -time algorithm even in sparse graphs (Roditty L, W…
View article: Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences Open
We study stable matching problems where agents have multilayer preferences: There are $\ell$ layers each consisting of one preference relation for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, es…
View article: Who won? Winner Determination and Robustness in Liquid Democracy
Who won? Winner Determination and Robustness in Liquid Democracy Open
Liquid democracy is a decision-making paradigm in which each agent can either vote directly for some alternative or (transitively) delegate its vote to another agent. To mitigate the issue of delegation cycles or the concentration of power…
View article: Fair Short Paths in Vertex-Colored Graphs
Fair Short Paths in Vertex-Colored Graphs Open
The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. For the setting where each vertex is assigned to a…
View article: Length-bounded cuts: Proper interval graphs and structural parameters
Length-bounded cuts: Proper interval graphs and structural parameters Open
We study the Length-Bounded Cut problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of at most β ed…
View article: Correction to: Parameterized Complexity of Min-Power Asymmetric Connectivity
Correction to: Parameterized Complexity of Min-Power Asymmetric Connectivity Open
A Correction to this paper has been published: https://doi.org/10.1007/s00224-021-10057-6
View article: Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments Open
We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex payi…
View article: A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem Open
The NP-hard Material Consumption Scheduling Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewabl…
View article: A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem Open
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewabl…