10.4230/LIPICS.STACS-NEW.2020.27
Mertzios, George B.
George B.
Mertzios
https://orcid.org/0000-0001-7182-585X
Department of Computer Science, Durham University, UK
Molter, Hendrik
Hendrik
Molter
https://orcid.org/0000-0002-4590-798X
TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Niedermeier, Rolf
Rolf
Niedermeier
https://orcid.org/0000-0003-1703-1236
TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Zamaraev, Viktor
Viktor
Zamaraev
https://orcid.org/0000-0001-5755-4141
Department of Computer Science, University of Liverpool, UK
Zschoche, Philipp
Philipp
Zschoche
https://orcid.org/0000-0001-9846-0600
TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Computing Maximum Matchings in Temporal Graphs
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
Conference Paper
Temporal Graph
Link Stream
Temporal Line Graph
NP-hardness
APX-hardness
Approximation Algorithm
Fixed-parameter Tractability
Independent Set
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
CNRS, Université de Montpellier, France
Markus Bläser
Universität des Saarlandes, Saarbrücken, Germany
arXiv:1905.05304
10.4230/LIPIcs.STACS-new.2020
978-3-95977-140-5
1868-8969
Creative Commons Attribution 3.0 Unported license
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 27:1-27:14