Suppose that we are doing a computer simulation of a dwarf kingdom. There is an underground labyrinth of some shape and size, inhabited by some number of dwarves. Every dwarf is arbitrarily moving around, but at all times obeying two laws of dwarf physics:
- The movement of dwarves must be continuous.
- The amount of dwarves must remain constant.
Given a specific setting of dwarves in a labyrinth, what can I know of their locations at some point in the future?
One formalization I can invent — follows:
$\textbf{definition}\quad$ Given a graph $G = (V, E)$ with some "selection" of vertices $S \subset V$, $S' \subset V$ is a "shift" of $S$ if they can be put into 1:1 correspondence so that the corresponding vertices are no more than 1 edge apart. $\square$
Then I ask whether we can enumerate all possible shifts of a given selection, and the number of ways each shift may be attained. This would allow us to probabilistically precompute the outcome of any number of shifts.
But I also see some analogy with, should I say, fluid dynamics: there are tangible, distinctly painted particles floating around in a continuum, obeying the same laws of continuity and preservation stated above — like some droplets of oil in a bowl of soup. Could this line of reasoning lead a more educated person than myself to some interesting quantitative results?
Is there some deep generalization here waiting to be discovered?
P.S. I have accepted an answer because it is actually an awesome solution to the problem in the formulation I had put forward. But I am still looking for some kind of unification with the continuous.
The problem boils down to enumerating perfect matchings in a bipartite graph.
For a set $S \subseteq V(G)$, construct an auxiliary bipartite graph - not quite a subgraph - as follows:
We should have $|A| \le |B|$ if there is any way for the dwarves to successfully move. Of course, you may allow the dwarves to sit still (approximating continuous motion along a path that goes nowhere), in which case all of $S$ is contained in $B$ as well, and this is guaranteed to hold.
A possible transition of the dwarves is a matching in this bipartite graph that saturates the vertices in $A$. Many people thinking about these problems like perfect matchings, which saturate both sides; we can obtain this by adding $|B|-|A|$ artificial vertices to $A$, which are adjacent to all of $B$. The artificial vertices will get matched to vertices of $B$ that are not the destination of any dwarf.
Unfortunately, counting perfect matchings in a graph is hard in general. This is one of the #P-complete problems: the equivalent of NP-complete, for counting problems rather than for decision problems.
Fortunately, we can go through all the perfect matchings in a way that takes $O(|S|)$ time per matching. This paper suggests several ways to do it. The problem is difficult mainly because there could be exponentially many perfect matchings. If you happen to have a dwarven network where the number of shifts is small for each $S$, then enumerating the shifts will not take long.
Finally, if you want to predict the dwarves' short-term state, this is going to be very hard with this approach, because the number of possible $S$ grows very quickly. However, long-term, the stationary distribution is relatively easy to describe: the probability of the dwarves occupying a set $S$ will be proportional to the number of shifts out of $S$.