<p>My friend Bastian and I devoted our bachelor's thesis to researching this problem. So I guess the problem has been researched (at least a little bit) now which answers my original question. Here is a link to the final result: <a href="http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Akth%3Adiva-166442" rel="nofollow" title="http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Akth%3Adiva-166442">The Monk Problem</a>. </p>

<p>Results include: </p>

<ul>
<li>New kind of recursive system (EL-systems) which is used as a verifier</li>
<li>Connection between search number and strongly connected components</li>
<li>Greedy heuristics based on graph decomposition</li>
</ul>

<p>The complexity class still remains unknown.</p>

CC BY-SA 3.0
2015-09-11T20:41:50.107Z
Thanks for posting this here! Hopefully I can find the time to take a look. Just wanted to point out that I found the recent work http://arxiv.org/abs/1502.05614 which studies a hunter and rabbit game: I think it is exactly your monk problem restricted to undirected graphs. They didn't seem to determine the complexity of computing the number of hunters required either, but maybe their work can interest you (or your work interest them?).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-09-20T13:40:33.373Z
Thanks for the comment! The problem seems to be the same but for undirected graphs as you say. I have not read the whole paper yet, but I look forward to do so!
Edvin
CC BY-SA 4.0
2022-04-22T20:38:05.633Z
A remark from thinking again about the problem, on undirected graphs, of deciding for fixed $k$ if $k$ pursuers suffice. I think for graphs of treewidth (maybe pathwidth) small wrt $k$, e.g., $\leq k/2$, you can win with $k$ pursuers following the tree dec. Conversely, for a graph of high treewidth $\geq k^100$, you can extract a subdivision of a wall as a topological minor (using https://arxiv.org/abs/1305.6577) and probably this witnesses that $k$ pursuers do not suffice. So I think the big question is whether the intermediate cases can be solved, i.e., for bounded treewidth.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-06-03T20:18:23.943Z
2015-06-03T20:18:23.943Z
Edvin
<p>Minimum number of cops (pursuer in your definition) needed to win in similar game is equivalent to <a href="http://www.sciencedirect.com/science/article/pii/S0304397508001588" rel="nofollow">Kelly width</a> of $G$, and it's NPC to determine that minimum number, it's similar to path decomposition for undirected graphs, but I don't know about minimum number of moves needed such that $k$ cop wins. But there are some works around similar games, if you are interested to know more about them maybe a good search term is cops and invisible inert robber game. Note that we can add loop to every vertex of a graph $G$ to skip the most move condition, then the game is in fact invisible robber game or the kelly width game or for undirected graph it's a well known path-width game (invisible robber is inert by nature). The maybe main difference between Kelly width game and this game is that robber can walk along edges not a single edge (I didn't read the question carefully at first, I read evader walks along edges, but still I don't think it makes totally different game, one may find a gadget to simulate walking along edge by walking along paths,  e.g something like turning vertices to complete graphs).</p>

CC BY-SA 3.0
2015-02-24T13:20:49.723Z
I don't understand the link to inert robber. In Edvin's definition the evaders *must*  move at each step, which makes all the difference. On an undirected 2-cycle, for 1 pursuer and 1 evader, in Edvin's formulation (where the evader *must* move at each step), the pursuer can win by examining twice the same vertex, but this crucially uses the fact that the evader must move at each time step.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-02-24T14:12:41.573Z
@a3nm, By having loop it's not important to say that robber should move. I updated the answer to reflect this. (invisible robber is inert by default, particularly OP mentioned it can walk through a loop).
Saeed
CC BY-SA 3.0
2015-02-28T15:09:57.183Z
There is another important difference between the problem definitions. In my version the cops do not have restricted movement (like Helicopter Cops and Robbers) but in the papers you mentioned (except the Kelly width paper) the cops must move along edges. I am looking closer at the paper on Kelly width, thank you for that.
Edvin
CC BY-SA 3.0
2015-02-28T20:15:43.230Z
@Edvin, right, I was much into considering allowance of only one edge move to check whether the complexity changes or not. By the way is robber visible for cops?
Saeed
CC BY-SA 3.0
2015-03-01T16:13:53.227Z
@Saeed No, the robber can be considered invisible.
Edvin
CC BY-SA 3.0
2015-03-03T09:52:55.033Z
@Saeed: Your answer still does not make sense to me. In Fomin, Golovach and Kratochvíl, the speed of the cops is bounded. The paper studies variants where the speed of the robber is infinite, but not of the cops. In Edvin's problem, the cops can teleport to any vertices at each turn. Could you please explain the relevance of Fomin, Golovach and Kratochvíl? Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-03-03T22:52:37.107Z
@a3nm that was my mistake, by Edvin's comment it became clear, I just didn't delete that part because later I'll check relevant papers and I'll edit the answer (e.g I just delete the new part as old part still is a little bit helpful, and I'll add new thing if I find something closer to edvin's game), but the reason that I didn't edit the question right now is that I don't want to make lots of edits, again as by edvin's comment it's clear.
Saeed
CC BY-SA 3.0
2015-03-03T23:00:03.723Z
Also by number of votes on question it seems the question is not interesting for big part of community (but it's quite interesting for me or maybe you and OP and some others) so I don't want to bring it up in the first page except I find good thing or I search enough and find nothing to delete probably the bad reference. Anyhow as edvin comment and my response to him made everything clear I didn't quite understand why you still looking for relevant.
Saeed
CC BY-SA 3.0
2015-03-03T23:41:20.007Z
@Saeed: I'm not sure I understand, but as it seems that your answer does not answer the question asked, I think it would be good policy to edit the answer, so that it states visibly, at the beginning, that it is not an answer to the question asked. It is probably not good that people have to dig in the comments to figure out that your answer does not answer the question. Second, as for edits bringing the question on the front page, I think you shouldn't worry. This is an interesting question, there is no point being ashamed if it turns up on the front page.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-03-04T01:28:34.180Z
@a3nm I thought you already read comments and then you left your comment. As you insist I edited the answer to leave it as it was before. If you think something is not clear or not correct feel free to tell me. But if you think kelly width is not a good start point then that's your opinion.
Saeed
CC BY-SA 3.0
2015-02-24T11:48:48.433Z
2015-03-04T01:32:02.933Z
2015-03-04T01:32:02.933Z
Saeed
<p>There are pursuers and evaders in the vertices of a directed graph G with one component.  Each vertex must have atleast one outgoing edge (can be a loop).</p>

<p>At each time t: </p>

<ul>
<li>The evaders must move along an edge to another vertex (may use loop)</li>
<li>Each pursuer must check one vertex (it can be any vertex in G).</li>
</ul>

<p>A vertex is considered contaminated at time <em>t</em> if an evader can be there without having been caught by the pursuers. A vertex <em>v</em> is decontaminated at time <em>t</em> if:</p>

<ul>
<li>A pursuer is checking <em>v</em>.</li>
<li>All edges to <em>v</em> originate from vertices which were decontaminated at time <em>t-1</em>.</li>
</ul>

<p>At time <em>t=0</em> all vertices are contaminated. The goal is that all vertices are decontaminated. This translates to the evaders being guaranteed to be caught.
A search strategy for <em>k</em> pursuers is a sequence of <em>k-tuples</em> referencing <em>k</em> vertices i.e. "check these <em>k</em> vertices at time <em>t=0</em>, then these <em>k</em> vertices at time <em>t=1</em>" and so on.</p>

<p>What is the minimum amount of pursuers needed to decontaminate all vertices in G?</p>

<p>What is the optimal (shortest sequence) search strategy given a graph G and k pursuers?</p>

<p><strong>So, where can I find this problem definition or an equal one? Is this problem NP-complete and if it is, how can that be shown?</strong> </p>

CC BY-SA 3.0
2015-02-24T00:12:10.793Z
This resembles problem F of http://pc.fdi.ucm.es/swerc/swerc10/SWERC-set.pdf : the monkey is the evader (there is only one evader) and the goal is to code a strategy for the pursuer that guarantees that the evader is caught (assuming that the input graph has such a strategy). For this case of 1 pursuer and 1 evader I think there was a PTIME test to determine whether the input graph did indeed have such a strategy. (This was not required by the problem I have linked.) Let me know if you want details.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-02-24T00:21:33.863Z
@Edvin: There is an inconsistency in the question formulation: do all vertices have an outgoing edge or not? One place say they do, the evader move rule assumes that it may not. Also note the following difference: in pc.fdi.ucm.es/swerc/swerc10/SWERC-set.pdf the graph is undirected, not directed, so that's one more restriction.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-02-24T00:32:27.270Z
@Edvin: Your question doesn't make it explicit, but am I right in thinking the number of evaders makes no difference in the existence of a decontamination sequence? If there is such a sequence that works for one evader, then it works for any number of evaders, right?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-02-24T11:13:16.813Z
@a3nm Yes, please give me details. I am working on a conjecture about the minimum amount of pursuers needed so that would be interesting to compare with the test. 
Thank you for pointing out the inconsistency. All vertices must have atleast one outgoing edge. 
And finally, yes you are correct, a sequence that works for one evader works for any number of evaders.
Edvin
CC BY-SA 3.0
2015-03-03T09:59:46.720Z
Edvin: I'm sorry that in fact I do not recall many details for one pursuer on undirected graphs. I think that if the graph contains a cycle then you cannot catch the evader. If there are no cycles, but there is a part of the graph that looks like a star with 3 branches of length 2 (o -- a1, a1 -- a2, o -- b1, b1 -- b2, o -- c1, c1 -- c2), then I think you cannot catch the evader either. Otherwise the graph is essentially a line graph with some additional nodes, which you can test in PTIME, but not sure if this was the exact criterion. Sorry for the dim memories. :/
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-03-08T10:29:55.597Z
My last comment is wrong, on a star graph with 3 branches of length 2 you can catch the evader (examine the middle of each branch and then the star center, repeat twice); it is on a star with 3 branches of length 3 that you cannot catch it.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-03-08T18:15:32.540Z
I was interested in trying out some small cases so I implemented a bruteforce search strategy to test examples http://a3nm.net/git/decontamination/tree/decontamination.cpp -- you're welcome to use it if it helps. Don't hesitate to ask if you can't get it to run (you can also contact me privately, as it's not convenient to do it in comments).
Antoine Amarilli 'a3nm'
<graph-theory><graph-algorithms>
Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game
Edvin
# Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

(Asked by: username_0 on 2015-02-23)

There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop).

At each time t:

* The evaders must move along an edge to another vertex (may use loop)
* Each pursuer must check one vertex (it can be any vertex in G).

A vertex is considered contaminated at time *t* if an evader can be there without having been caught by the pursuers. A vertex *v* is decontaminated at time *t* if:

* A pursuer is checking *v*.
* All edges to *v* originate from vertices which were decontaminated at time *t-1*.

At time *t=0* all vertices are contaminated. The goal is that all vertices are decontaminated. This translates to the evaders being guaranteed to be caught.
A search strategy for *k* pursuers is a sequence of *k-tuples* referencing *k* vertices i.e. "check these *k* vertices at time *t=0*, then these *k* vertices at time *t=1*" and so on.

What is the minimum amount of pursuers needed to decontaminate all vertices in G?

What is the optimal (shortest sequence) search strategy given a graph G and k pursuers?

**So, where can I find this problem definition or an equal one? Is this problem NP-complete and if it is, how can that be shown?**

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: This resembles problem F of http://pc.fdi.ucm.es/swerc/swerc10/SWERC-set.pdf : the monkey is the evader (there is only one evader) and the goal is to code a strategy for the pursuer that guarantees that the evader is caught (assuming that the input graph has such a strategy). For this case of 1 pursuer and 1 evader I think there was a PTIME test to determine whether the input graph did indeed have such a strategy. (This was not required by the problem I have linked.) Let me know if you want details.  
> **username_1**: @username_0: There is an inconsistency in the question formulation: do all vertices have an outgoing edge or not? One place say they do, the evader move rule assumes that it may not. Also note the following difference: in pc.fdi.ucm.es/swerc/swerc10/SWERC-set.pdf the graph is undirected, not directed, so that's one more restriction.  
> **username_1**: @username_0: Your question doesn't make it explicit, but am I right in thinking the number of evaders makes no difference in the existence of a decontamination sequence? If there is such a sequence that works for one evader, then it works for any number of evaders, right?  
> **username_0**: @a3nm Yes, please give me details. I am working on a conjecture about the minimum amount of pursuers needed so that would be interesting to compare with the test.  Thank you for pointing out the inconsistency. All vertices must have atleast one outgoing edge.  And finally, yes you are correct, a sequence that works for one evader works for any number of evaders.  
> **username_1**: username_0: I'm sorry that in fact I do not recall many details for one pursuer on undirected graphs. I think that if the graph contains a cycle then you cannot catch the evader. If there are no cycles, but there is a part of the graph that looks like a star with 3 branches of length 2 (o -- a1, a1 -- a2, o -- b1, b1 -- b2, o -- c1, c1 -- c2), then I think you cannot catch the evader either. Otherwise the graph is essentially a line graph with some additional nodes, which you can test in PTIME, but not sure if this was the exact criterion. Sorry for the dim memories. :/  
> **username_1**: My last comment is wrong, on a star graph with 3 branches of length 2 you can catch the evader (examine the middle of each branch and then the star center, repeat twice); it is on a star with 3 branches of length 3 that you cannot catch it.  
> **username_1**: I was interested in trying out some small cases so I implemented a bruteforce search strategy to test examples http://a3nm.net/git/decontamination/tree/decontamination.cpp -- you're welcome to use it if it helps. Don't hesitate to ask if you can't get it to run (you can also contact me privately, as it's not convenient to do it in comments).  

---

## 2 answers

### Answer by username_0 on 2015-06-03. Score: 1 | Accepted answer

My friend Bastian and I devoted our bachelor's thesis to researching this problem. So I guess the problem has been researched (at least a little bit) now which answers my original question. Here is a link to the final result: [The Monk Problem](http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Akth%3Adiva-166442 "http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Akth%3Adiva-166442").

Results include:

* New kind of recursive system (EL-systems) which is used as a verifier
* Connection between search number and strongly connected components
* Greedy heuristics based on graph decomposition

The complexity class still remains unknown.

> **Comments:**
> **username_1**: Thanks for posting this here! Hopefully I can find the time to take a look. Just wanted to point out that I found the recent work http://arxiv.org/abs/1502.05614 which studies a hunter and rabbit game: I think it is exactly your monk problem restricted to undirected graphs. They didn't seem to determine the complexity of computing the number of hunters required either, but maybe their work can interest you (or your work interest them?).  
> **username_0**: Thanks for the comment! The problem seems to be the same but for undirected graphs as you say. I have not read the whole paper yet, but I look forward to do so!  
> **username_1**: A remark from thinking again about the problem, on undirected graphs, of deciding for fixed $k$ if $k$ pursuers suffice. I think for graphs of treewidth (maybe pathwidth) small wrt $k$, e.g., $\leq k/2$, you can win with $k$ pursuers following the tree dec. Conversely, for a graph of high treewidth $\geq k^100$, you can extract a subdivision of a wall as a topological minor (using https://arxiv.org/abs/1305.6577) and probably this witnesses that $k$ pursuers do not suffice. So I think the big question is whether the intermediate cases can be solved, i.e., for bounded treewidth.  

---

### Answer by username_2 on 2015-02-24. Score: 0

Minimum number of cops (pursuer in your definition) needed to win in similar game is equivalent to [Kelly width](http://www.sciencedirect.com/science/article/pii/S0304397508001588) of $G$, and it's NPC to determine that minimum number, it's similar to path decomposition for undirected graphs, but I don't know about minimum number of moves needed such that $k$ cop wins. But there are some works around similar games, if you are interested to know more about them maybe a good search term is cops and invisible inert robber game. Note that we can add loop to every vertex of a graph $G$ to skip the most move condition, then the game is in fact invisible robber game or the kelly width game or for undirected graph it's a well known path-width game (invisible robber is inert by nature). The maybe main difference between Kelly width game and this game is that robber can walk along edges not a single edge (I didn't read the question carefully at first, I read evader walks along edges, but still I don't think it makes totally different game, one may find a gadget to simulate walking along edge by walking along paths, e.g something like turning vertices to complete graphs).

> **Comments:**
> **username_1**: I don't understand the link to inert robber. In username_0's definition the evaders *must*  move at each step, which makes all the difference. On an undirected 2-cycle, for 1 pursuer and 1 evader, in username_0's formulation (where the evader *must* move at each step), the pursuer can win by examining twice the same vertex, but this crucially uses the fact that the evader must move at each time step.  
> **username_2**: @a3nm, By having loop it's not important to say that robber should move. I updated the answer to reflect this. (invisible robber is inert by default, particularly OP mentioned it can walk through a loop).  
> **username_0**: There is another important difference between the problem definitions. In my version the cops do not have restricted movement (like Helicopter Cops and Robbers) but in the papers you mentioned (except the Kelly width paper) the cops must move along edges. I am looking closer at the paper on Kelly width, thank you for that.  
> **username_2**: @username_0, right, I was much into considering allowance of only one edge move to check whether the complexity changes or not. By the way is robber visible for cops?  
> **username_0**: @username_2 No, the robber can be considered invisible.  
> **username_1**: @username_2: Your answer still does not make sense to me. In Fomin, Golovach and Kratochvíl, the speed of the cops is bounded. The paper studies variants where the speed of the robber is infinite, but not of the cops. In username_0's problem, the cops can teleport to any vertices at each turn. Could you please explain the relevance of Fomin, Golovach and Kratochvíl? Thanks!  
> **username_2**: @a3nm that was my mistake, by username_0's comment it became clear, I just didn't delete that part because later I'll check relevant papers and I'll edit the answer (e.g I just delete the new part as old part still is a little bit helpful, and I'll add new thing if I find something closer to edvin's game), but the reason that I didn't edit the question right now is that I don't want to make lots of edits, again as by edvin's comment it's clear.  
> **username_2**: Also by number of votes on question it seems the question is not interesting for big part of community (but it's quite interesting for me or maybe you and OP and some others) so I don't want to bring it up in the first page except I find good thing or I search enough and find nothing to delete probably the bad reference. Anyhow as edvin comment and my response to him made everything clear I didn't quite understand why you still looking for relevant.  
> **username_1**: @username_2: I'm not sure I understand, but as it seems that your answer does not answer the question asked, I think it would be good policy to edit the answer, so that it states visibly, at the beginning, that it is not an answer to the question asked. It is probably not good that people have to dig in the comments to figure out that your answer does not answer the question. Second, as for edits bringing the question on the front page, I think you shouldn't worry. This is an interesting question, there is no point being ashamed if it turns up on the front page.  
> **username_2**: @a3nm I thought you already read comments and then you left your comment. As you insist I edited the answer to leave it as it was before. If you think something is not clear or not correct feel free to tell me. But if you think kelly width is not a good start point then that's your opinion.  

---

