首页 | 本学科首页   官方微博 | 高级检索  
     


Parameterized algorithm for eternal vertex cover
Authors:Fedor V Fomin  Serge Gaspers  Dieter Kratsch
Affiliation:a Department of Informatics, University of Bergen, N-5020 Bergen, Norway
b CMM - Universidad de Chile, Av. Blanco Encalada 2120, Santiago, Chile
c School of Engineering and Computing Sciences, Durham University, South Road, DH1 3LE Durham, UK
d Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045 Metz Cedex 01, France
e The Institute of Mathematical Sciences, CIT Campus, Chennai 600 113, India
Abstract:In this paper we initiate the study of a “dynamic” variant of the classical Vertex Cover problem, the Eternal Vertex Cover problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size k4(k+1)+2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(2O(k2)+nm) for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that Eternal Vertex Cover is NP-hard, yet it has a polynomial time 2-approximation algorithm.
Keywords:Graph algorithms  Parameterized complexity  Fixed parameter tractability  Vertex cover  Eternal vertex cover
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号