Monday, July 4, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture
Abstract:
A temporal graph is a graph that changes over time. Assuming discrete time and a fixed set V of vertices, a temporal graph can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different and substantially more difficult when the time dimension is additionally taken into account. In this talk we will introduce temporal graphs and we will survey recent algorithmic results.
Colloquium - 16:00
Parameterized complexity analysis is a flourishing field dealing with the exact solvability of "intractable" problems. But why should this natural and successful approach be limited to NP-hard problems? Appropriately parameterizing polynomial-time solvable problems helps reducing unattractive polynomial running times. In particular, this "FPT in P" approach sheds new light on what makes a problem far from being solvable in linear time, in the same way as classical FPT algorithms help in illuminating what makes an NP-hard problem far from being solvable in polynomial time. Surprisingly, this very interesting research direction has been too little explored so far; the known results are rather scattered and do not systematically refer to or exploit the toolbox of parameterized algorithm design.
In this talk we introduce the field of "FPT in P". To this end, we outline known results, explain the corresponding techniques, and highlight similarities and differences to the classical design of parameterized algorithms for NP-hard problems. Finally we present our recent work with George Mertzios and Rolf Niedermeier on parameterized algorithms for maximum cardinality matching.