Computing maximum matchings in temporal graphs

Mertzios, G.B.; Molter, H.; Niedermeier, R.; Zamaraev, V.; Zschoche, P.

doi:10.1016/j.jcss.2023.04.005

Computing maximum matchings in temporal graphs

Mertzios, G.B.; Molter, H.; Niedermeier, R.; Zamaraev, V.; Zschoche, P.

Authors

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

H. Molter

R. Niedermeier

V. Zamaraev

P. Zschoche

Abstract

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 ∆ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms.

Citation

Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, https://doi.org/10.1016/j.jcss.2023.04.005

Journal Article Type	Article
Acceptance Date	Apr 21, 2023
Online Publication Date	May 4, 2023
Publication Date	2023
Deposit Date	May 10, 2023
Publicly Available Date	May 5, 2024
Journal	Journal of Computer and System Sciences
Print ISSN	0022-0000
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
DOI	https://doi.org/10.1016/j.jcss.2023.04.005
Public URL	https://durham-repository.worktribe.com/output/1173066