2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ This resembles problem F of 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. $\endgroup$
    – a3nm
    Feb 24, 2015 at 0:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – a3nm
    Feb 24, 2015 at 0:21
  • 1
    $\begingroup$ @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? $\endgroup$
    – a3nm
    Feb 24, 2015 at 0:32
  • $\begingroup$ @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. $\endgroup$
    – Edvin
    Feb 24, 2015 at 11:13
  • $\begingroup$ 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. :/ $\endgroup$
    – a3nm
    Mar 3, 2015 at 9:59

2 Answers 2

Reset to default
1
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 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?). $\endgroup$
    – a3nm
    Sep 11, 2015 at 20:41
  • $\begingroup$ 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! $\endgroup$
    – Edvin
    Sep 20, 2015 at 13:40
  • $\begingroup$ 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 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. $\endgroup$
    – a3nm
    Apr 22 at 20:38
0
$\begingroup$

Minimum number of cops (pursuer in your definition) needed to win in similar game is equivalent to Kelly width 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).

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Feb 24, 2015 at 13:20
  • $\begingroup$ @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). $\endgroup$
    – Saeed
    Feb 24, 2015 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – Edvin
    Feb 28, 2015 at 15:09
  • $\begingroup$ @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? $\endgroup$
    – Saeed
    Feb 28, 2015 at 20:15
  • $\begingroup$ @Saeed No, the robber can be considered invisible. $\endgroup$
    – Edvin
    Mar 1, 2015 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.