文章基本信息

标题：Computing Maximum Matchings in Temporal Graphs
本地全文：下载
作者：George B. Mertzios ; Hendrik Molter ; Rolf Niedermeier 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：27:1-27:14
DOI：10.4230/LIPIcs.STACS.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Temporal Graph; Link Stream; Temporal Line Graph; NP-hardness; APX-hardness; Approximation Algorithm; Fixed-parameter Tractability; Independent Set