Matthias Bentert

TCS Journal 2026 Journal Article

The parameterized complexity landscape of two-sets cut-uncut

• Matthias Bentert
• Fedor V. Fomin
• Fanny Hauser
• Saket Saurabh

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 graph (V, E∖C), the terminals in each terminal set remain in the same connected component. In spite of the superficial similarity to the classic problem Minimum s-t-Cut, Two-Sets Cut-Uncut is computationally challenging. In particular, even deciding whether such a cut of any size exists, is already NP-complete. We initiate a systematic study of Two-Sets Cut-Uncut within the context of parameterized complexity. By leveraging known relations between many well-studied graph parameters, we characterize the structural properties of input graphs that allow for polynomial kernels, fixed-parameter tractability (FPT), and slicewise polynomial algorithms (XP). Our main contribution is the near-complete establishment of the complexity of these algorithmic properties within the described hierarchy of graph parameters. On a technical level, our main results are fixed-parameter tractability for the (vertex-deletion) distance to cographs and an OR-cross composition excluding polynomial kernels for the vertex cover number of the input graph (under the standard complexity assumption NP ¬ ⊆ coNP/poly).

TCS Journal 2026 Journal Article

When does FTP become FPT?

• Matthias Bentert
• Fedor V. Fomin
• Petr A. Golovach
• Laure Morelle

In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = ( V, E ), a subset U⊆E of vulnerable edges, two vertices s, t ∈ V, and integers k and ℓ. The task is to decide whether there exists a subgraph H of G with total cost at most ℓ such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include: the number of vulnerable edges in the input graph, the number of safe (i. e, invulnerable) edges in the input graph, the budget ℓ, the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters.

IJCAI Conference 2025 Conference Paper

How to Resolve Envy by Adding Goods

• Matthias Bentert
• Robert Bredereck
• Eva Deltl
• Pallavi Jain
• Leon Kellerhals

We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomial-time algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists—an aspect that is both theoretically interesting and far from trivial.

SODA Conference 2025 Conference Paper

Packing Short Cycles

• Matthias Bentert
• Fedor V. Fomin
• Petr A. Golovach
• Tuukka Korhonen
• William Lochet
• Fahad Panolan
• M. S. Ramanujan 0001
• Saket Saurabh 0001

MFCS Conference 2024 Conference Paper

Breaking a Graph into Connected Components with Small Dominating Sets

• Matthias Bentert
• Michael R. Fellows
• Petr A. Golovach
• Frances A. Rosamond
• Saket Saurabh 0001

We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V, E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which each connected component has a dominating set of size at most d. We also consider the special case where d is a constant. We show an almost complete tetrachotomy in terms of para-NP-hardness, containment in XP, containment in FPT, and admitting a polynomial kernel with respect to parameterizations that are a combination of k, d, c, and Δ, where c and Δ are the degeneracy and the maximum degree of the input graph, respectively. As a main contribution, we show that the problem can be solved in f(k, d) ⋅ n^O(d) time, that is, the problem is FPT when parameterized by k when d is a constant. This answers an open problem asked in a recent Dagstuhl seminar (23331). For the special case d = 1, we provide an algorithm with running time 2^𝒪(klog k) nm. Furthermore, we show that even for d = 1, the problem does not admit a polynomial kernel with respect to k + c.

AAAI Conference 2023 Conference Paper

Fair Short Paths in Vertex-Colored Graphs

• Matthias Bentert
• Leon Kellerhals
• Rolf Niedermeier

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 group (color), we provide a framework to model multiple natural fairness aspects. We seek to find short paths in which the number of occurrences of each color is within some given lower and upper bounds. Among other results, we prove the introduced problems to be computationally intractable (NP-hard and parameterized hard with respect to the number of colors) even in very restricted settings (such as each color should appear with exactly the same frequency), while also presenting an encouraging algorithmic result ("fixed-parameter tractability") related to the length of the sought solution path for the general problem.

TCS Journal 2022 Journal Article

The structural complexity landscape of finding balance-fair shortest paths

• Matthias Bentert
• Leon Kellerhals
• Rolf Niedermeier

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. We provide an almost complete picture of the parameterized complexity landscape of the problem with respect to structural parameters by showing a tetrachotomy including polynomial kernels, fixed-parameter tractability, XP-time algorithms (and W [ 1 ] -hardness), and para-NP-hardness.

AAAI Conference 2021 Conference Paper

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem

• Matthias Bentert
• Robert Bredereck
• Péter Györgyi
• Andrzej Kaczmarczyk
• Rolf Niedermeier

The NP-hard MATERIAL CONSUMPTION SCHEDULING PROBLEM and 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-renewable resources. We focus on the singlemachine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized computational complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational complexity. Thereby, we get a deepened understanding of this fundamental scheduling problem.

AAAI Conference 2020 Conference Paper

Comparing Election Methods Where Each Voter Ranks Only Few Candidates

• Matthias Bentert
• Piotr Skowron

Election rules are formal processes that aggregate voters’ preferences, typically to select a single winning candidate. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized—we ask each voter to rank a random subset of candidates, and (ii) deterministic—we ask each voter to provide a ranking of her most preferred candidates (the -truncated ballot). We establish theoretical bounds on the approximation ratios and complement our theoretical analysis with computer simulations. We find that it is usually better to use the randomized approach.