Computing maximum matchings in temporal graphs

Mertzios, George B, Molter, Hendrik, Niedermeier, Rolf, Zamaraev, Viktor ORCID: 0000-0001-5755-4141 and Zschoche, Philipp (2023) Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, 137. pp. 1-19.

Text main.pdf - Author Accepted Manuscript Access to this file is embargoed until 4 May 2024. Download (521kB)

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.

Item Type:	Article
Uncontrolled Keywords:	Link streams, Temporal line graphs, NP -hardness, APX-hardness, Approximation algorithms, Fixed -Parameter tractability, Kernelization, Independent set
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	02 Jun 2023 07:02
Last Modified:	12 Jul 2023 22:57
DOI:	10.1016/j.jcss.2023.04.005
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3170786