ETERNAL VERTEX COVER OF BIPARTITE AND CO-BIPARTITE GRAPHS

JASINE BABU (Indian Institute of Technology Palakkad)

NEELDHARA MISRA (Indian Institute of Technology Gandhinagar)

SARASWATI GIRISH NANOTI (Indian Institute of Technology Gandhinagar)

ETERNAL VERTEX COVER NUMBER

• Dynamic variant of the vertex cover problem.
• Guards are placed on some vertices of a graph.
• In every move, the attacker attacks an edge. In response, the defender moves the guards along the edges in such a manner that at least one guard moves along the attacked edge.
• If such a movement is not possible, attacker wins. If the defender can defend an infinite sequence of attacks, defender wins.
• The minimum number of guards with which defender has a winning strategy is called the Eternal Vertex Cover Number of the Graph G known as evc(G).

An Example:�

BACKGROUND AND �MOTIVATION �

MINIMUM VERTEX COVER NUMBER OF A GRAPH

CONNECTED VERTEX COVER NUMBER OF A GRAPH

KNOWN RESULTS ABOUT THE EVC NUMBER

• Introduced by Klostermeyer and Mynhardt in 2009.
• Showed that mvc(G) ≤ evc(G) ≤ 2mvc(G).
• Gave a characterization of graphs for which upper bound is achieved. The characterization of graphs for which lower bound is achieved remains open.
• Babu et al gave a such a characterization for some graph classes including chordal graphs and internally triangulated planar graphs.

ALGORITHMIC RESULTS ABOUT THE EVC NUMBER

RED BLUE DOMINATING SET

GIVEN:

A bipartite graph G = (B ∪ R, E) and an integer k.

TO FIND:

If there exists a vertex set S ⊆ R of size at most k such that every vertex in B has at least one neighbor in S.

In the literature, the sets B and R are called “blue” and “red vertices”, respectively.

It is known that RBDS parameterized by (|B|, k) does not have a polynomial kernel, and more generally, a polynomial compression, unless co-NP ⊆ NP/poly. (Fomin et al., 2019).

ETERNAL VERTEX COVER PROBLEM FOR BIPARTITE GRAPHS

MAIN RESULT:

There is a polynomial parameter transformation from Red Blue Dominating Set parameterized by |B| + k to Eternal Vertex Cover parameterized by solution size.

A TYPICAL INSTANCE OF RED BLUE DOMINATING SET:

CONSTURCTION OF THE NEWLY CONSTRUCTED GRAPH

The vertex cover number of H is b + 1.

Any vertex cover of H that has at most ℓ vertices must contain B ∪ {⋆}.

THE FORWARD DIRECTION: AN ILLUSTRATION

⟨G = (V, E), k⟩ is a Yes-instance of Red Blue Dominating Set ⇒ ⟨H, ℓ⟩ is a Yes-instance of Eternal Vertex Cover. 

• Recall that G has an RBDS of size k and ℓ=b+k+2.
• Any VC of size b+k+2 must have all the blue vertices and the universal vertex.
• We maintain the invariant the all the vertices corresponding to the RBDS of G must have a guard.

​

PROOF OUTLINE FOR THE FORWARD DIRECTION

• ⟨G = (V, E), k⟩ is a Yes-instance of Red Blue Dominating Set ⇒ ⟨H, ℓ⟩ is a Yes-instance of Eternal Vertex Cover. 
• Let S ⊆ V(G) be a dominating set of G. 
• WLOG S = {v₁, . . . , v_k }. 
• Let S^⋆ := {v₁, . . . , v_k } ⊆ A, i.e., the red vertices of H corresponding to the solution in G.

​

From Klostermeyer and Mynhardt (2009), we have evc(H) ⩽ cvc(H) + 1.

Using the previous claim, we get evc(H) ⩽ b + k + 2 i.e. evc(H) ⩽ ℓ. Thus ⟨H, ℓ⟩ is a YES-instance of ETERNAL VERTEX COVER.

If G has a red blue dominating set of size k, then the connected vertex cover number of H is at least b + k + 1.

PROOF OUTLINE OF THE BACKWARD DIRECTION

⟨H, ℓ⟩ is a Yes-instance of Eternal Vertex Cover ⇒ ⟨G = (V, E), k⟩ is a Yes-instance of Red Blue Dominating Set.

• Any sequence of edge attacks in H can be defended by deploying at most ℓ = b + k + 2 guards.

​

• Let S denote the initial placement of guards.

​

• We now consider two cases:

​

• S contains the backup vertex : We show that the set of red vertices who have a guard or who have a blue neighbor whose dependent neighbours have a guard forms a dominating set of size k or less.

​

• S does not contain the backup vertex: We attack the bridge edge and guards are forced to form a configuration in case 1.

RESULTS FOR BIPARTITE GRAPHS

• ETERNAL VERTEX COVER is unlikely to admit a polynomial compression parametrized by the number of guards, even on bipartite graphs of diameter 6.
• Also works for ETERNAL CONNECTED VERTEX COVER.
• Both ETERNAL VERTEX COVER and ETERNAL CONNECTED VERTEX COVER are NP-hard even on bipartite graphs of diameter 6.
• Both ETERNAL VERTEX COVER and ETERNAL CONNECTED VERTEX COVER are unlikely to admit a polynomial kernel even on bipartite graphs of diameter 6.

ETERNAL VERTEX COVER PROBLEM FOR CO-BIPARTITE GRAPHS

MAIN RESULT FOR CO-BIPARTITE GRAPHS

There is a polynomial-time (quadratic) algorithm for ETERNAL VERTEX COVER on the class of co-bipartite graphs.

• G: Co-bipartite graph with bipartition A,B
• A and B: Cliques
• |A|=p, |B|=q, p ⩽ q
• No vertex in B is universal

For any co-bipartite graph G which is not a clique with bipartitions A and B, if there are no universal vertices in B, mvc(G)=p+q−2.

• mvc(G) = p + q − 2 and p + q − 2 ⩽ evc(G) ⩽ p + q − 1.

​

• Use the PSPACE algorithm given by Fomin et al. (2010).

​

• Runtime can be improved to O(n²) as follows:
• evc(G)=p+q-2 if and only if A and B both contain at least two non-cut non-universal vertices.
• Existence of cut vertices and universal vertices can be checked in O(n²) time.

ILLUSTRATION OF AN ATTACK AND A DEFENSE

CONCLUDING REMARKS AND FUTURE DIRECTIONS:

• The hardness of Eternal Vertex Cover on bipartite graphs�of constant diameter.

​

• Under standard complexity-theoretic assumptions, the problem does not admit a polynomial compression on these graph classes when parameterized by the number of guards.

​

• This also implies hardness when paramterized by the vertex cover number.

​

• It will be interesting to pursue improved FPT and approximation algorithms for these classes of graphs.

​

• It is also unclear if Eternal Vertex Cover is in NP even on these classes of graphs.

REFERENCES:

• Jasine Babu, L. Sunil Chandran, Mathew C. Francis, Veena Prabhakaran, Deepak Rajendraprasad, and Nandini J Warrier. On graphs whose eternal vertex cover number and vertex cover number coincide. Discrete Applied Mathematics (in press), 2021.

​

• Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Dieter Kratsch, and Saket Saurabh. Parameterized algorithm for eternal vertex cover. Information Processing Letters, 110(16):702–706, 2010.

​

• Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019.

​

• William F. Klostermeyer and Christina M. Mynhardt. Edge protection in graphs. Australas. J Comb., 45:235–250, 2009

THANK YOU