19 citations · 118 across the 26 of their papers we have counts for
38 papers
Parameterizing Cluster Editing by the Number of Deletions
Vincent Froese, Leon Kellerhals, Frank Sommer +2
In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn into a disjoint union of cliques. Komusiewicz and…
Parameterized Complexity of Temporal Agony
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +1
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarch…
Computational Complexity of the Interval Ordering Problem
Simeon Pawlowski, Vincent Froese
We study an interval ordering problem introduced by Dürr et al. [Discrete Appl. Math. 2012] which is motivated by applications in bioinformatics. The task is to order a given set o…
Parameterized Algorithms for Computing MAD Trees
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +2
We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem whi…
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese +2
We study -Bounded-Density Edge Deletion (-BDED), where given an undirected graph , the task is to remove as few edges as possible to obtain a graph where no subgraph…
Nash Equilibria in Reverse Temporal Voronoi Games
Simeon Pawlowski, Vincent Froese
We study Voronoi games on temporal graphs as introduced by Boehmer et al. (IJCAI 2021) where two players each select a vertex in a temporal graph with the goal of reaching the othe…
Training Neural Networks is NP-Hard in Fixed Dimension
Vincent Froese, Christoph Hertrich
We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and l…
Terrain-like Graphs and the Median Genocchi Numbers
Vincent Froese, Malte Renken
A graph with vertex set is terrain-like if, for any edge pair with , the edge also exists. Terrain-like graphs frequently appe…
There and Back Again: On Applying Data Reduction Rules by Undoing Others
Aleksander Figiel, Vincent Froese, André Nichterlein +1
Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm th…
Disentangling the Computational Complexity of Network Untangling
Vincent Froese, Pascal Kunz, Philipp Zschoche
We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set cha…
Modification-Fair Cluster Editing
Vincent Froese, Leon Kellerhals, Rolf Niedermeier
The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge mod…
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Vincent Froese, Christoph Hertrich, Rolf Niedermeier
Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps an…
Equilibria in Schelling Games: Computational Hardness and Robustness
Luca Kreisel, Niclas Boehmer, Vincent Froese +1
In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maxim…
Two Influence Maximization Games on Graphs Made Temporal
Niclas Boehmer, Vincent Froese, Julia Henkel +3
To address the dynamic nature of real-world networks, we generalize competitive diffusion games and Voronoi games from static to temporal graphs, where edges may appear or disappea…
Parameterized Algorithms for Matrix Completion With Radius Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix shall have limited (local) radius. In the pure radius ve…
Faster Binary Mean Computation Under Dynamic Time Warping
Nathan Schaar, Vincent Froese, Rolf Niedermeier
Many consensus string problems are based on Hamming distance. We replace Hamming distance by the more flexible (e.g., easily coping with different input string lengths) dynamic tim…
The Complexity of Binary Matrix Completion Under Diameter Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resul…
Mathematical Programming Models for Mean Computation in Dynamic Time Warping Spaces
Vincent Froese, Christoph Hansknecht
The dynamic time warping (dtw) distance is an established tool for mining time series data. The DTW-Mean problem consists of computing a series which minimizes the so-called Fréche…
Persistent Graphs and Cyclic Polytope Triangulations
Vincent Froese, Malte Renken
We prove a bijection between the triangulations of the 3-dimensional cyclic polytope C(n+2, 3) and persistent graphs with n vertices. We show that under this bijection the Stasheff…
An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping
Brijnesh Jain, Vincent Froese, David Schultz
Computing a sample mean of time series under dynamic time warping (DTW) is NP-hard. Consequently, there is an ongoing research effort to devise efficient heuristics. The majority o…
Good Things Come to Those Who Swap Objects on Paths
Matthias Bentert, Jiehua Chen, Vincent Froese +1
We study a simple exchange market, introduced by Gourvés, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the o…
Advancing Through Terrains
Vincent Froese, Malte Renken
We study terrain visibility graphs, a well-known graph class closely related to polygon visibility graphs in computational geometry, for which a precise graph-theoretical character…
Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
Vincent Froese, Brijnesh Jain, Maciej Rymar +1
Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length- time series,…
Comparing Temporal Graphs Using Dynamic Time Warping
Vincent Froese, Brijnesh Jain, Rolf Niedermeier +1
Within many real-world networks the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal…