Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework that—for any subgraph problem of a certain type—guarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t-Path, Perfect Matching, Minimum s-t-Cut—and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages.

Abstract In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs.