Prof. Dr. Tobias Friedrich

Research Seminar (Winter Term 2018)

<previous seminar | next seminar>


A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich or to Ralf Rothenberger.


For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

Date Room Speaker Title
11.10. 11:00 H-E.52 Martin Schirneck

A reoccurring task in the design and profiling of relational data is the discovery of hidden dependencies between attributes. Enumerating those dependencies is equivalent to the transversal hypergraph problem. We devise a backtracking algorithm for the enumeration of inclusion-wise minimal hitting sets. It achieves polynomial delay on hypergraphs for which the size of the largest minimal transversal is bounded. The algorithm solves the extension problem for minimal hitting sets as a subroutine. Although this problem is NP-complete and W[3]-complete in general, we show that a careful implementation of the extension oracle can help avoiding the worst case on hypergraphs arising in the profiling of real-world databases, leading to significant speed-ups in practice.

This is joint work with Thomas Bläsius, Tobias Friedrich, Julius Lischeid, and Kitty Meeks.

14.11. 16:00 G3-E.15/16 Patrick Schäfer

A time series (TS) is a collection of values sequentially ordered in time. TS emerge in many scientific and commercial applications. One driving force behind their rising importance is the sharply increasing usage of sensors for automatic and high resolution monitoring in domains such as smart homes, machine surveillance, land cover mapping using satellite images, smart grids, weather observations, wind energy forecasting, mobility tracking, etc.

The main purpose of TS analytics is to extract meaningful knowledge based on the shape of the TS data, which implies exploiting temporal order. Though humans have some natural capacity to solve the identification of perceptually similar but not mathematically identical TS, this remains a complex problem for computers.

In this talk, I will provide an overview of the techniques applied for TS analytics, where approaches can broadly be divided into Whole Series, Shapelets, Dictionary (Bag-of-Patterns), Ensembles, and Deep-Learning. With a focus on TS classification, I will address how state-of-the-art approaches represent the fundamental shapes of a TS and how these features are used. The talk ends with an experimental evaluation of the state-of-the-art classification approaches.

15.11. 15:00 A-2.1 Marianne Thieffry

Many real-world networks share common properties like power law degree distribution, small diameters, and large clustering coefficients. Graph models used in research try to mimic real-world networks by providing similar properties. Hyperbolic random graphs in particular have recently gained popularity in network research because they implement all mentioned properties. However, generators for hyperbolic random graphs only support a limited number of dimensions for the underlying geometry, resulting in tight links between average node degree and clustering coefficients. A generalization of hyperbolic random graphs are geometric inhomogeneous random graphs (GIRGs), pro- posed by Bringmann et al. They also present a sampling algorithm to generate GIRGs that has an expected running time of O(n) that supports an arbitrary number of dimensions in the underlying geometry.

In this Thesis, we explain GIRGs and the sampling algorithm as proposed by Bringmann et al. We present the first implementation of a graph generator with underlying geometry that supports an an arbitrary numbers of dimensions. We suggest some enhancements to the sampling algorithm proposed by Bringmann et al. to boost the run-time of the generator by 20%. We also theoretically analyze configurations for the sampling algorithm to give the user of our tool more direct control of the output. Finally, we use our implementation to empirically validate theoretical findings on GIRGs.

15.11. 16:00 A-2.1 Sven Ihde

Networks are a fundamental part of our society. The recent development of devices shows that more and more networks are experiencing a shift from wire-lined to wireless ad-hoc networks. Such networks exist in numerous forms and are from a multitude of different domains. By using the tools and explanatory power of Game Theory, we explore the creation and properties of such networks.

In this work we look at Wireless Network Creation Games, where selfish agents build an ad-hoc network. In contrast to most current research on this topic, which only tries to minimize the energy consumption of an agent, we also analyse the quality of an agent’s connection by creating a trade-off between energy consumption and experienced service quality. Because of that we define multiple games by additionally imposing a parameter similar to the hop distance of internet networking, which is used to measure the real-time performance and stability of connections in a network. In these games we study Nash Equilibria, as well as the resulting dynamics created by the behaviour of selfish agents. We also provide an approximation algorithm that efficiently converges and provide empirical evidence to show that the resulting states of the Wireless Network Creation Game are close to optimal. Furthermore, we analyse the social welfare of these networks to illustrate how the selfish behaviour of agents influences the well-being of society.

23.11. 11:00 A-1.1 Katrin Casel

The very general problem of determining the quality of a given partial solution occurs basically in every algorithmic approach which computes solutions in some sense gradually. Pruning search-trees, proving approximation guarantees or the efficiency of enumeration strategies usually requires a suitable way to decide if a partial solution is a reasonable candidate to pursue. Consider for example the classical concept of minimal dominating sets for graphs. The task of finding a maximum cardinality minimal dominating set (or an approximation of it) as well as enumerating all minimal dominating sets naturally leads to solving the following extension problem: Given a graph G=(V,E) and a subset P of V, does there exists a minimal dominating set S for G which contains P.
In an attempt to study the nature of such extension tasks, we propose a general, partial-order based framework to express a broad class of what we refer to as extension problems. In essence, we consider optimisation problems in NPO with an additionally specified set of presolutions (including the solutions) and a partial order on those. We consider a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a presolution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the presolution. We further discuss relaxation of the extension constraint asking only for a solution S which preserves as much of P as possible. These considerations yield some insight into the various difficult aspects of extension problems.

14.12. 11:00 A-1.1 Thomas Sauerwald
Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress the coalescence time for graphs such as binary trees, d-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log^2 n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O(n^3) (which is tight for the Barbell graph); surprisingly even such a basic question about the coalescing time was not answered before this work. By duality, our results give bounds on the voter model and therefore give bounds on the consensus time in arbitrary undirected graphs. We also establish a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.
07.01. 15:15 H-2.58 Manuel Penschuck