Open Access
- 29 April 2022
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 66 (2) , 454-483
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.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (NI/369-18)
This publication has 28 references indexed in Scilit:
- Fast Dynamic Graph Algorithms for Parameterized Problems2014
- Changing Bases: Multistage Optimization for Matroids and Matchings2014
- Facility Location in Evolving Metrics2014
- Time-varying graphs and dynamic networksInternational Journal of Parallel, Emergent and Distributed Systems, 2012
- On the complexity of reconfiguration problemsTheoretical Computer Science, 2011
- Maximum independent sets in 3- and 4-regular Hamiltonian graphsDiscrete Mathematics, 2010
- On problems without polynomial kernelsJournal of Computer and System Sciences, 2009
- The Connectivity of Boolean Satisfiability: Computational and Structural DichotomiesSIAM Journal on Computing, 2009
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976