Cops, a fast robber and defensive domination on interval graphs (Q2328864)

The authors in this paper have considered the original and its generalized version of Cops and Robber game in combinatorial graph theory stated as follows: It is played by $k$ cops managed by one player and one robber managed by the other player on a given simple undirected graph $G$. The cops and the robber are stationed on vertices of $G$ at any time; several cops are allowed to share a vertex. Both players have a thorough information about $G$ and the game state. At the beginning of the game, the cops pick beginning vertices, then the robber picks a beginning vertex. If there is no vertex for the robber, the cops win and the game is over. A step is a move of a cop to distance at most one (being stationary on the same vertex is permitted). One turn then consists of a cop-move, where every cop makes a step, followed by a robber-move, where the robber moves along any cop-free path of length one. (If that cop free path is of length s where s is greater than or equal to one then it is a generalized version of this original problem). The robber may never pass through a vertex where a cop is present. In the generalized case of s approaching infinity the robber may move to an arbitrary vertex of his current component of $G \setminus C$ where $C$ is the (multi)set of cops' position. If a cop be at or move to robber's vertex then the game is over and the robber is captured. The robber wins by avoiding the capture indefinitely. The minimum number of cops sufficient to capture the robber in a graph $G$ is denoted by $c(G)$ in the original version and $c_s(G)$ in the generalized version. The authors solved the open problem about the computational complexity of the game on interval graphs with infinity fast robber, establishing that the problem can be decided in polynomial time. They then also generalized the concept of $k$-defensive domination introduced by Farley and Proskurowski in ``Defensive Domination'' to $\mathcal{A}$-defensive domination and established that $\mathcal{A}$-defensive domination is also solvable in polynomial time on interval graphs where by $k$-defensive domination we mean the following. The input is a graph $G$ and an integer $k$. A simple set $D \subseteq V_G$ is said to be $k$-defensive dominating if for each set $\{a_1, \dots, a_k\} \subseteq V_G$ of $k$ distinct vertices of $G$ (called a $k$-attack) there exists a set $\{d_1, \dots, d_k\} \subseteq D$ of $k$ distinct vertices of $D$ (called an assignment of defenders) such that for each $i \in \{ 1, \dots, k\}$ we have $d_i \in N[a_i]$. The goal is to find a $k$-defensive dominating set $D$ of minimum size and by a $\mathcal{A}$-defensive domination the authors mean the following. Input: Graph $G$, a family of vertex multisets $\mathcal{A}$ (the attacks) and vertex multisets $D_{min} \subseteq D_{max}$. Output: A smallest multiset of vertices $D$ defending every attack $A \in \mathcal{A}$ such that $D_{min}\subseteq D \subseteq D_{max}$, or information that no such $D$ exists. The proof technique employed by the authors is both wonderful and comprehensive.