Preprint
Abstract
Covering all edges of a graph by a small number of vertices, this is the NP-complete Vertex Cover problem. It is among the most fundamental 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 the most natural parameterizations.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Approximating Multistage Matching ProblemsAlgorithmica, 2022
- LP-Based Algorithms for Multistage Minimization Problems2021
- Multistage graph problems on a global budgetTheoretical Computer Science, 2021
- Temporal graph classes: A view through temporal separatorsTheoretical Computer Science, 2020
- Dynamic Parameterized ProblemsAlgorithmica, 2017
- Incremental list coloring of graphs, parameterized by conservationTheoretical Computer Science, 2013
- Time-varying graphs and dynamic networksInternational Journal of Parallel, Emergent and Distributed Systems, 2012
- Maximum independent sets in 3- and 4-regular Hamiltonian graphsDiscrete Mathematics, 2010
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976