On the parameterized complexity of dynamic problems

In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what "remained" from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a solution is bounded by some increment-parameter. Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including VERTEX COVER, MAXIMUM CLIQUE, CONNECTED VERTEX COVER and CONNECTED DOMINATING SET. In particular, we show that DYNAMIC VERTEX COVER is W[1]-hard, and the connected versions of both DYNAMIC VERTEX COVER and DYNAMIC DOMINATING SET become fixed-parameter tractable with respect to the edit-parameter while they remain W[2]-hard with respect to the increment-parameter. Moreover, we show that DYNAMIC INDEPENDENT DOMINATING SET is W[2]-hard with respect to the edit-parameter. We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while DYNAMIC MAXIMUM CLIQUE is fixed-parameter tractable with respect to the edit-parameter, it becomes W[1]-hard if the increment-parameter is replaced with the reoptimization parameter. Finally, we establish that DYNAMIC DOMINATING SET becomes W[2]-hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one. (C) 2015 Elsevier B.V. All rights reserved.