2019/06/03 by Till Fluschnik, Rolf Niedermeier, Fluschnik, Till +5 · 1 citation
Computer Science · #68Q17 #68Q25 #68R10 #68W40 #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Interconnection Networks and Systems #Opportunistic and Delay-Tolerant Networks
paper · doi:10.48550/arxiv.1906.00659
openalex publication_date 2019/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.