Executive Summary : | The Vertex Cover (VC) problem is a central problem in optimization and computer science due to both its theoretical significance and practical applications. A graph is described by its vertices and edges, where each edge is an unordered pair of vertices called the endpoints of the edge. Informally, a vertex cover of a graph G is a subset S of its vertices such that by placing guards only on vertices of S, all edges of G are protected (that is, at least one of the endpoints of each edge has a guard). Formally, a vertex cover of a graph G is a subset S of its vertices such that for every edge e of G, at least one of the endpoints of e belongs to S. The objective of the VC problem is to find a vertex cover of G of minimum number of elements. Eternal Vertex Cover (EVC) problem is a dynamic reconfiguration extension of the VC problem, where instead of remaining stationary, the guard positions need a dynamic transition among different vertex covers, for handling attacks. The problem is expressed as an attacker-defender game of multiple rounds. The number of guards remain the same throughout the game. The defender has the freedom to initially place guards on vertices of his choice. In each round, the attacker chooses to attack any one edge of his choice. To defend the attack, at least one guard, which must have been present at an end point of the attacked edge prior to the attack, has to move across that edge. Other guards may also move to vertices adjacent to their current positions; but the movements must be such that a future attack on any edge can be successfully defended. The eternal vertex cover number (evc number) of G, denoted by evc(G) is the minimum number of guards k such that any infinite rounds of attacks on G can be defended with k guards. Unlike the VC decision problem, deciding whether evc number of an arbitrary graph G is at most k is not known to be in NP, though both problems are known to be NP-hard. The VC problem is polynomial time solvable for bipartite graphs. However, the complexity status of computation of evc number of bipartite graphs is a well-known open problem since 2010. From the insights from our prior work, we think that the problem is likely to be NP-hard for bipartite graphs. If this is proven, it will support the general belief that the EVC problem is computationally much harder than the VC problem. Computing the evc number of trees is easy. However, it has been an open problem since 2010 as to whether evc number of constant treewidth graphs (a generalization of trees) can be computed in polynomial time. We think this can be done, by extending the techniques we used for designing a recursive algorithm for cactus graphs. The EVC problem of internally triangulated planar graphs is NP-hard and has a PTAS. Whether for planar graphs the problem is in NP and whether it has a PTAS are open. The proposal is to solve these open problems, building on our previous work and techniques from the literature. |