Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-15783
For citation please use:
Main Title: Multistage vertex cover
Author(s): Fluschnik, Till
Niedermeier, Rolf
Rohm, Valentin
Zschoche, Philipp
Type: Article
URI: https://depositonce.tu-berlin.de/handle/11303/17004
http://dx.doi.org/10.14279/depositonce-15783
License: https://creativecommons.org/licenses/by/4.0/
Abstract: The NP-complete Vertex Cover problem asks to cover all edges of a graph by a small (given) number of vertices. It is among the most prominent graph-algorithmic problems. Following a recent trend in studying temporal graphs (a sequence of graphs, so-called layers, over the same vertex set but, over time, changing edge sets), we initiate the study of Multistage Vertex Cover. Herein, given a temporal graph, the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that two vertex cover sets of every two consecutive layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of themost natural parameterizations.
Subject(s): parameterized algorithmics
NP-completeness
temporal graphs
data reduction
Issue Date: 29-Apr-2022
Date Available: 25-May-2022
Language Code: en
DDC Class: 510 Mathematik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2022
Journal Title: Theory of Computing Systems
Publisher: Springer Nature
Volume: 66
Publisher DOI: 10.1007/s00224-022-10069-w
Page Start: 454
Page End: 483
EISSN: 1433-0490
ISSN: 1432-4350
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatik » FG Algorithmik und Komplexitätstheorie
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons