Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these initial set of vertices are globally known to all agents. At each step, the agents can traverse an edge connected to their current vertex. If the agent happens to arrive at a vertex $v$ which was previously unvisited by any player, then all the edges connected to $v$ becomes global knowledge to all agents. The aim of the agents is to reach a vertex $v_G$, it suffices if any one agent reaches $v_G$.

I was wondering if this community can point me to problems that have a similar flavor in literature that has been studied before.

One interesting question would be to find the minimum number of steps required to reach $v_G$. I can think of a simple Dynamic Programming(DP) based algorithm for computing the minimum number of steps. A state in the DP would be, the number of steps elapsed, the vertices visited by all agents and the current vertex occupied by each agent. It is simple to expand these states and compute the minimum number of steps. However the number of states expanded can be exponential in $|V|, |A|, M$. I am wondering if one can do better than the DP sketch I just described. More formally, what is the complexity in determining the minimum number of steps.

  • $\begingroup$ This sounds like a random walk aka Markov chain. Even if the agents behave deterministically, that can be modeled with transition probabilities that are all either 0 or 1. $\endgroup$ – Sebastian Oberhoff Mar 17 '18 at 1:13
  • 1
    $\begingroup$ I guess the lack of answers to this question is caused by it being unclear what you're asking. How is this "game" anything other than a simple modification of BFS? What are the game elements here? What do you want to achieve? $\endgroup$ – Pål GD Mar 18 '18 at 18:33
  • $\begingroup$ @PålGD - I agree, I have modified the question. $\endgroup$ – csTheoryBeginner Mar 19 '18 at 15:35
  • 1
    $\begingroup$ I don't understand the statement of dynamic programming, nor NP-hardness. The problem you are describing is not well-defined, or if you just want to minimize number of steps, any algorithm is as good as any other. $\endgroup$ – Pål GD Mar 19 '18 at 22:06
  • $\begingroup$ @PålGD - Hopefully it is more clear now. I was of the opinion that the problem I described may have been studied in certain communities, hence originally just asked for relevant literature. Most probably I am mistaken. $\endgroup$ – csTheoryBeginner Mar 19 '18 at 23:18

Your Answer

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

Browse other questions tagged or ask your own question.