Algorithmik und Komplexitätstheorie
Institut für Softwaretechnik und Theoretische Informatik
Fakultät Elektrotechnik und Informatik
Technische Universität Berlin
Sekr. TEL 5-1
Ernst Reuter Platz 7
D-10587 Berlin
Email: till.fluschnik 'at' tu-berlin 'dot' de
PhD student

Publications.

2019.

Authors Title Journal Conference arxiv
TF, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche Temporal Graph Classes: A View Through Temporal Separators
abstract

We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s, z)-Separation problem is NP-hard, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph---there we observe polynomial-time solvability in the case of bounded treewidth---as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.

accepted at TCS (SI) WG 2018: 216-227 arXiv
Matthias Bentert, TF, André Nichterlein, and Rolf Niedermeier Parameterized Aspects of Triangle Enumeration
abstract

Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter).

JCSS(SI) 103:61-77 (2019) FCT 2017: 10472:96–110 arXiv
TF, Marco Morik, and Manuel Sorge The Complexity of Routing with Few Collisions
abstract

We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph G with two distinct terminal vertices and two positive integers p and k, the question is whether one can connect the terminals by at least p routes (e.g. paths) such that at most k edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if k is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary k and on directed graphs if k is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs.

JCSS(SI) 102: 69-86 (2019) FCT 2017: 10472:257–270 arXiv
TF, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge The Parameterized Complexity of the Minimum Shared Edges Problem accepted at JCSS FSTTCS 2015: 448-462 arxiv (2016)
René van Bevern, TF, Oxana Y. Tsidulko On (1+ε)-approximate problem kernels for the Rural Postman Problem accepted at MOTOR 2019 arXiv
TF, Piotr Skowron, Mervin Triphaus, Kai Wilker Fair Knapsack
abstract

We study the following multiagent variant of the knapsack problem. We are given a set of items, a set of voters, and a value of the budget; each item is endowed with a cost and each voter assigns to each item a certain value. The goal is to select a subset of items with the total cost not exceeding the budget, in a way that is consistent with the voters' preferences. Since the preferences of the voters over the items can vary significantly, we need a way of aggregating these preferences, in order to select the socially most preferred valid knapsack. We study three approaches to aggregating voters preferences, which are motivated by the literature on multiwinner elections and fair allocation. This way we introduce the concepts of individually best, diverse, and fair knapsack. We study computational complexity (including parameterized complexity, and complexity under restricted domains) of computing the aforementioned concepts of multiagent knapsacks.

accepted for publication (AAAI) arXiv (2017+)
TF, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon When can Graph Hyperbolicity be computed in Linear Time? accepted at Algorithmica WADS 2017: 10389:397–408 arXiv
Markus Brill, TF, Vincent Froese, Brijnesh Jain, Rolf Niedermeier, and David Schultz Exact Mean Computation in Dynamic Time Warping Spaces
abstract

Dynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minimizing the Fr\'echet function) is a challenging computational problem, so far solved by several heuristic, inexact strategies. We spot several inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Our contributions comprise an exact dynamic program computing a mean (useful for benchmarking and evaluating known heuristics). Empirical evaluations reveal significant deficits of the state-of-the-art heuristics in terms of their output quality. Finally, we give an exact polynomial-time algorithm for the special case of binary time series.

Data Min. Knowl. Discov. 33(1): 252-291 SDM 2018: 540–548 arXiv (2017)

2018.

Authors Title Journal Conference Other
René van Bevern, TF, Oxana Yu. Tsidulko Parameterized algorithms and data reduction for safe convoy routing
abstract

We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph $G=(V,E)$, two vertices $s,t\in V$, and two integers $k,\ell$, we search for a simple $s$-$t$-path with at most $k$ vertices and at most $\ell$ neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential $2^{O(\sqrt n)}$-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a $2^{O(\mathrm{tw})}\cdot \ell^2\cdot n$-time algorithm for graphs of treewidth $\mathrm{tw}$, show that there is no problem kernel with size polynomial in $\mathrm{tw}$, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.

under review ATMOS 2018: 10:1-10:19 arxiv (2018)
Max-Jonathan Luckow, TF On the computational complexity of length- and neighborhood-constrained path problems
------
arxiv
Cristina Bazgan, TF, André Nichterlein, Rolf Niedermeier, and Maximilian Stahlberg A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths Networks 73(1):23-37 (2019)
------
arxiv
René van Bevern, TF, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondřej Suchý The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs Discrete Optimization 30: 20-50 (2018) IPEC 2016: 5:1-5:16 arXiv (2017)
TF, Danny Hermelin, André Nichterlein, and Rolf Niedermeier Fractals for Kernelization Lower Bounds SIAM J. Discrete Math., 32(1), 656-681 (2018) ICALP 2016: (55)25:1-25:14 arxiv (2017)
TF, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche Temporal Graph Classes: A View Through Temporal Separators
abstract

We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s, z)-Separation problem is NP-hard, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph---there we observe polynomial-time solvability in the case of bounded treewidth---as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.

accepted at TCS (SI) WG 2018: 216-227 arXiv
Philipp Zschoche, TF, Hendrik Molter, and Rolf Niedermeier The Complexity of Finding Small Separators in Temporal Graphs
abstract

Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that contain arbitrarily many edges per time step (non- strict) and paths that contain at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial- time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.

under review MFCS 2018: 45:1-45:17 arXiv
Markus Brill, TF, Vincent Froese, Brijnesh Jain, Rolf Niedermeier, and David Schultz Exact Mean Computation in Dynamic Time Warping Spaces
abstract

Dynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minimizing the Fr\'echet function) is a challenging computational problem, so far solved by several heuristic, inexact strategies. We spot several inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Our contributions comprise an exact dynamic program computing a mean (useful for benchmarking and evaluating known heuristics). Empirical evaluations reveal significant deficits of the state-of-the-art heuristics in terms of their output quality. Finally, we give an exact polynomial-time algorithm for the special case of binary time series.

Data Min. Knowl. Discov. 33(1): 252-291 SDM 2018: 540–548 arXiv (2017)
Henning Fernau, TF, Danny Hermelin, Andreas Krebs, Hendrik Molter, and Rolf Niedermeier Diminishable Parameterized Problems and Strict Polynomial Kernelization under review CiE 2018: 10936:161–171 arXiv
TF, George B. Mertzios, and André Nichterlein Kernelization Lower Bounds for Finding Constant Size Subgraphs
abstract

Kernelization is an important tool in parameterized algorithmics. The goal is to reduce the input instance of a parameterized problem in polynomial time to an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture.

CiE 2018: 10936:183–193 arXiv

2017.

Authors Title Journal Conference arxiv
TF, Marco Morik, and Manuel Sorge The Complexity of Routing with Few Collisions
abstract

We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph G with two distinct terminal vertices and two positive integers p and k, the question is whether one can connect the terminals by at least p routes (e.g. paths) such that at most k edges are time-wise shared among them. We study three types of routes: traverse each vertex at most once (paths), each edge at most once (trails), or no such restrictions (walks). We prove that for paths and trails the problem is NP-complete on undirected and directed graphs even if k is constant or the maximum vertex degree in the input graph is constant. For walks, however, it is solvable in polynomial time on undirected graphs for arbitrary k and on directed graphs if k is constant. We additionally study for all route types a variant of the problem where the maximum length of a route is restricted by some given upper bound. We prove that this length-restricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NP-complete on undirected graphs.

accepted at JCSS (SI) FCT 2017: 10472:257–270 arXiv
Matthias Bentert, TF, André Nichterlein, and Rolf Niedermeier Parameterized Aspects of Triangle Enumeration
abstract

Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter).

accepted at JCSS (SI) FCT 2017: 10472:96–110 arXiv
TF, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon When can Graph Hyperbolicity be computed in Linear Time? accepted at Algorithmica WADS 2017: 10389:397–408 arXiv
TF, Meike Hatzel, Steffen Härtlein, Hendrik Molter, and Henning Seidler The Minimum Shared Edges Problem on Grid-like Graphs
abstract

We study the 𝖭𝖯-hard Minimum Shared Edges (MSE) problem on graphs: decide whether it is possible to route p paths from a start vertex to a target vertex in a given graph while using at most k edges more than once. We show that MSE can be decided on bounded (i.e. finite) grids in linear time when both dimensions are either small or large compared to the number p of paths. On the contrary, we show that MSE remains 𝖭𝖯-hard on subgraphs of bounded grids. Finally, we study MSE from a parametrised complexity point of view. It is known that MSE is fixed-parameter tractable with respect to the number p of paths. We show that, under standard complexity-theoretical assumptions, the problem parametrised by the combined parameter k, p, maximum degree, diameter, and treewidth does not admit a polynomial-size problem kernel, even when restricted to planar graphs.

WG 2017: 10520:249–262 arXiv

2016.

Authors Title Journal Conference arxiv
René van Bevern, TF, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondřej Suchý The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs Discrete Optimization 30: 20-50 (2018) IPEC 2016: 5:1-5:16 arXiv (2017)
TF, Steffen Kriewald, Anselmo García Cantú Ros, Bin Zhou, Dominik E. Reusser, Jürgen P. Kropp, and Diego Rybski The Size Distribution, Scaling Properties and Spatial Organization of Urban Clusters: A Global and Regional Perspective IJGI, ISPRS Int. J. Geo-Inf. 2016, 5(7), 110
------
arxiv (2014)
TF, Danny Hermelin, André Nichterlein, and Rolf Niedermeier Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems SIAM J. Discrete Math., 32(1), 656-681 (2018) ICALP 2016: (55)25:1-25:14 arxiv (2017)
TF and Manuel Sorge The Minimum Shared Edges Problem on Planar Graphs
------
------
arXiv
Ramana Venkata Gudipudi, TF, Anselmo García Cantú Ros, Carsten Walther, and Jürgen P. Kropp City Density and CO2 Efficiency
abstract

Cities play a vital role in the global climate change mitigation agenda. City population density is one of the key factors that influence urban energy consumption and the subsequent GHG emissions. However, previous research on the relationship between population density and GHG emissions led to contradictory results due to urban/rural definition conundrum and the varying methodologies for estimating GHG emissions. This work addresses these ambiguities by employing the City Clustering Algorithm (CCA) and utilizing the gridded CO2 emissions data. Our results, derived from the analysis of all inhabited areas in the US, show a sub-linear relationship between population density and the total emissions (i.e. the sum of on-road and building emissions) on a per capita basis. Accordingly, we find that doubling the population density would entail a reduction in the total CO2 emissions in buildings and on-road sectors typically by at least 42%. Moreover, we find that population density exerts a higher influence on on-road emissions than buildings emissions. From an energy consumption point of view, our results suggest that on-going urban sprawl will lead to an increase in on-road energy consumption in cities and therefore stresses the importance of developing adequate local policy measures to limit urban sprawl.

Energy Policy, (91)352–361
------
------

2015.

Authors Title Journal Conference arxiv
TF, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge The Parameterized Complexity of the Minimum Shared Edges Problem accepted at JCSS FSTTCS 2015: 448-462 arxiv (2016)

2014.

Authors Title Journal Conference arxiv
Anselmo García Cantú Ros, TF, and Jürgen P. Kropp Variance-based control of regime shifts: bistability and oscillations under review
------
arXiv

Theses.

Master Thesis.

Bachelor Thesis.

TF. Kritisches Verhalten eines verdünnten zufälligen Polymers. TU Berlin.

Participant.

2018.

 18th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS '18). In Helsinki, Finland, August 23 – 24 , 2018. © Till Fluschnik Dagstuhl Seminar 18281: Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices. In Dagstuhl, Germany, July 8 – 13 , 2018. © Till Fluschnik 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'18). In Lübbenau, Germany, June 27-29, 2018. © Till Fluschnik

2017.

 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17). In Eindhoven, The Netherlands, June 21-23, 2017. © Till Fluschnik

2015.

 Workshop on Kernelization (WORKER) 2015. In Nordfjordeid, Norway. June 2015. © Till Fluschnik

Talks.

2019.

 33rd AAAI Conference on Artificial Intelligence (AAAI '18) . Honolulu, Hawaii, USA, Jan 27-Feb 01 © Till Fluschnik

2018.

 Conference on Computability in Europe (CiE'18) . Kiel, Germany, July 30-August 3 © Till Fluschnik SIAM International Conference on Data Mining 2018 (SDM'18) . San Diego, CA, USA, May 3-5 75. Workshop über Algorithmen und Komplexität . Universität Ulm, Ulm, Germany, April 10-11 © Till Fluschnik

2017.

 74. Workshop über Algorithmen und Komplexität . Universität zu Lübeck, Lübeck, Germany, November 23-24 © Till Fluschnik 15th Algorithms and Data Structures Symposium (WADS) . St. John's, Newfundland, Canada, July 31-August 2 © Till Fluschnik

2016.

 72. Workshop über Algorithmen und Komplexität . Leibniz Universität Hannover, Institut für Theoretische Informatik. © Till Fluschnik 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) . In Aarhus, Denmark, August 24-26. © Till Fluschnik 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016). In Rome, Italy. July 2016. © Till Fluschnik

2015.

 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). In Bangalore, India. December 2015. © Till Fluschnik 7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW). In Aussois, France. October 2015. Slides. © Till Fluschnik The size distribution, scaling properties and spatial organization of urban clusters: a global and regional perspective. Verhandlungen der Deutschen Physikalischen Gesellschaft, AKE 14: Physics of Sustainability and Human-Nature Interactions I, at TU Berlin, Germany. March 2015.

Co-Supervised Theses.

2018.

Leon Kellerhals. Parameterized Algorithms for Network Flows. TU Berlin, June 2018, Master thesis.

Valentin Rohm. Vertex Cover Under Time Constraints. TU Berlin, November 2018, Bachelor thesis.

2017.

Philipp Zschoche. On Finding Separators in Temporal Graphs. TU Berlin, August 2017, Master thesis.

Max-Jonathan Luckow. Paths under Neighborhood Constraints — Algorithms and Complexity. TU Berlin, April 2017, Bachelor thesis.

2016.

Matthias Bentert. Parametrised Algorithms for Finding Triangles in Graphs - Detection, Counting and Enumeration. TU Berlin, December 2016, Master thesis.

Marco Morik. The Complexity of Routing with Collision Avoidance. TU Berlin, June, 2016. Bachelor thesis.

Maximilian Stahlberg. Finding the Most Vital Edges for Shortest Paths - Algorithms and Complexity for Special Graph Classes. TU Berlin, February, 2016. Bachelor thesis.

Misc.

Script Recommendations (for Lectures etc.).

Analysis (and more) Scripts by Dirk Ferus (only in German).

Scripts by Wolfgang König (in the context of probabilistic theory, only in German): in particular, Wahrscheinlichkeitstheorie I+II and Stochastische Algorithmen.

Script by Stefan Felsner (together with students) about Graph theory (only in German)

Book Recommendations.

Martin Aigner and Günter M. Ziegler: Proof from THE BOOK