TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 31.10.2019


Page Content

to Navigation

Computing Maximum Matchings in Temporal Graphs

Hendrik Molter (TU Berlin)


We study the computational complexity of finding maximum-cardinality temporal matchings in temporal graphs (where the edge set may change over time while the vertex set remains fixed). Our model of temporal matching (which seems to be slightly more general than a previous one due to Baste et al. [Theor. Comp. Sci., 2019]) allows capturing several real-world scenarios where (as e.g. in social networks) relations change over time and where one also has to model the duration of pairings between agents. In this paper we present several classic and approximation hardness results as well as approximation and exact fixed-parameter algorithms, thus improving several parts of previous work of Baste et al. We show hardness already for very restricted cases and introduce temporal line graphs as a concept of independent interest. Altogether, our results both show the various degrees of computational intractability of "temporal matching" and point to some islands of tractability which may give hope for efficient solutions in relevant special cases. Our work focuses on exploring the computational complexity landscape (tractable versus intractable) and mainly delivers classification results.

Based on joint work with George B. Mertzios, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche.


Hendrik Molter
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe