2017.
Authors  Title  Journal  Conference  arxiv 

TF, Piotr Skowron, Mervin Triphaus, Kai Wilker  Fair Knapsack
abstractWe 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. 
arXiv  
Philipp Zschoche, TF, Hendrik Molter, and Rolf Niedermeier  The Computational Complexity of Finding Separators in Temporal Graphs
abstractVertex separators, that is, vertex sets whose deletion disconnects two distinguished vertices in a graph, play a pivotal role in algorithmic graph theory. For instance, the concept of tree decompositions of graphs is tightly connected to the separator concept. For many realistic models of the real world, however, it is necessary to consider graphs whose edge set changes with time. More specifically, the edges are labeled with time stamps. In the literature, these graphs are referred to as temporal graphs, temporal networks, timevarying networks, edgescheduled networks, etc. While there is an extensive literature on separators in "static" graphs, much less is known for the temporal setting. Building on previous work (e.g., Kempe et al. [STOC '00]), for the first time we systematically investigate the (parameterized) complexity of finding separators in temporal graphs. Doing so, we discover a rich landscape of computationally (fixedparameter) tractable and intractable cases. In particular, we shed light on the so far seemingly overlooked fact that two frequently used models of temporal separation may lead to quite significant differences in terms of computational complexity. More specifically, considering paths in temporal graphs one may distinguish between strict paths (the time stamps along a path are strictly increasing) and nonstrict paths (the time stamps along a path are monotonically nondecreasing). We observe that the corresponding strict case of temporal separators leads to several computationally much easier to handle cases than the nonstrict case does. 
arXiv  
Markus Brill, TF, Vincent Froese, Brijnesh Jain, Rolf Niedermeier, and David Schultz  Exact Mean Computation in Dynamic Time Warping Spaces
abstractDynamic 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 stateoftheart heuristics in terms of their output quality. Finally, we give an exact polynomialtime algorithm for the special case of binary time series. 
arXiv  
TF, George B. Mertzios, and André Nichterlein  Kernelization Lower Bounds for Finding Constant Size Subgraphs
abstractKernelization 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 polynomialtime 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 lineartime computable strict kernel of truly subcubic size for this problem violates the popular APSPconjecture. 
arXiv  
TF, Marco Morik, and Manuel Sorge  The Complexity of Routing with Few Collisions
abstractWe 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 timewise 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 NPcomplete 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 lengthrestricted variant has the same complexity classification with respect to paths and trails, but for walks it becomes NPcomplete on undirected graphs. 
FCT 2017: 10472:257–270  arXiv (bibdblp)  
Matthias Bentert, TF, André Nichterlein, and 
Parameterized Aspects of Triangle Enumeration
abstractListing 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 worstcase 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). 
FCT 2017: 10472:96–110, (Best Student Paper Award)  arXiv (bibdblp)  
TF, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and 
When can Graph Hyperbolicity be computed in Linear Time?  WADS 2017: 10389:397–408  arXiv  
TF, Meike Hatzel, Steffen Härtlein, Hendrik Molter, and Henning Seidler  The Minimum Shared Edges Problem on Gridlike Graphs
abstractWe 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 fixedparameter tractable with respect to the number p of paths. We show that, under standard complexitytheoretical assumptions, the problem parametrised by the combined parameter k, p, maximum degree, diameter, and treewidth does not admit a polynomialsize problem kernel, even when restricted to planar graphs. 
WG 2017: 10520:249–262  arXiv  
Henning Fernau, TF, Danny Hermelin, 
Diminishable Parameterized Problems and Strict Polynomial Kernelization  arXiv 
2016.
Authors  Title  Journal  Conference  arxiv 

René van Bevern, TF, George B. Mertzios, 
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs  under review  IPEC 2016: 5:15: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. GeoInf. 2016, 5(7), 110  arxiv (2014)  
TF, Danny Hermelin, André Nichterlein, and 
Fractals for Kernelization Lower Bounds, With an Application to LengthBounded Cut Problems  under review  ICALP 2016: (55)25:125:14  arxiv (2015) 
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
abstractCities 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 sublinear relationship between population density and the total emissions (i.e. the sum of onroad 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 onroad sectors typically by at least 42%. Moreover, we find that population density exerts a higher influence on onroad emissions than buildings emissions. From an energy consumption point of view, our results suggest that ongoing urban sprawl will lead to an increase in onroad 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 
The Parameterized Complexity of the Minimum Shared Edges Problem  under review  FSTTCS 2015: 448462  arxiv (2016) 
2014.
Authors  Title  Journal  Conference  arxiv 

Anselmo García Cantú Ros, TF, and Jürgen P. Kropp  Variancebased control of regime shifts: bistability and oscillations  under review  arXiv 
Master Thesis.
TF. The Parameterized Complexity of Finding Paths with Shared Edges. TU Berlin.
Bachelor Thesis.
TF. Kritisches Verhalten eines verdünnten zufälligen Polymers. TU Berlin.
2017.
43rd International Workshop on GraphTheoretic Concepts in Computer Science (WG'17). In Eindhoven, The Netherlands, June 2123, 2017. 
2015.
Workshop on Kernelization (WORKER) 2015. In Nordfjordeid, Norway. June 2015. 

2017.
15th Algorithms and Data Structures Symposium (WADS) . St. John's, Newfundland, Canada, July 31August 2 

2016.
72. Workshop über Algorithmen und Komplexität . Leibniz Universität Hannover, Institut für Theoretische Informatik. 

11th International Symposium on Parameterized and Exact Computation (IPEC 2016) . In Aarhus, Denmark, August 2426. 

43rd International Colloquium on Automata, Languages and Programming (ICALP 2016). In Rome, Italy. July 2016. 

2015.
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). In Bangalore, India. December 2015. 

7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW). In Aussois, France. October 2015. Slides. 

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 HumanNature Interactions I, at TU Berlin, Germany. March 2015. 
2017.
MaxJonathan 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.
Maximilian Stahlberg. Finding the Most Vital Edges for Shortest Paths  Algorithms and Complexity for Special Graph Classes. TU Berlin, February, 2016. Bachelor thesis.
Marco Morik. The Complexity of Routing with Collision Avoidance. TU Berlin, June, 2016. Bachelor thesis.
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)
Martin Aigner and Günter M. Ziegler: Proof from THE BOOK
TÜV Rheinland Berlin MarathonRelay
Orthodromic Spatial Clustering