$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $i$-th coordinate being $1$ and other coordinates being $0$.
(3)A vertex $v \in V$ is a $n$-dimensional vector belonging to $(\{0\} \cup [m])^n$ whose $n-1$ coordinates are $0$ and one coordinate is non-zero. For example $[1, 0, 0]$ is a vertex while $[1, 1, 0]$ is not. There are $mn$ vertices.
(4)A state $s \in (\{0\} \cup [m])^n$ is a set of vertices: $\{s_i \neq 0|[0, 0, \dots, \underbrace{s_i}_{i\text{-th}\,coordinate}, 0, 0, \dots, 0] \in V\}$. There are $(m+1)^n$ states in total.
The edges connect vertices in $V$. We say a state $s$ is a deadlock iff one of the following two conditions:
(1) $\exists x, y \in s$ such that $xy \in E$. (Explicit law)
(2) $\forall i \in [m]$, $s + e_i$ is a deadlock. (Recursive law)
I want to find an efficient algorithm which is polynomial w.r.t $|E|$ to determine whether a state $s$ is a deadlock, or prove this problem is $NP$ or $NP$-hard.
$\textbf{II. Background and Examples}$
I know this problem looks weird but it has a very practical background. Consider $n$ vehicles moving along $n$ distinct paths whose lengths are $m$. Each vehicle is a vertex and a set of vehicles is a state. For each time we can ask one vehicle to move one step. However, due to geometric constraints, e.g., narrow roads, vertices might pairwise conflict, so there are deadlocks.
To be convenient, I define the $\text{Next}(s)$ operator: It adds the non-zero coordinates of $s$ by $1$ without changing the $0$ coordinates, for example $\text{Next}([5, 2, 0]) = [6, 3, 0]$.
For the first example, $\{a, b, c\}$ forms a deadlock. $ab, bc, ca$ are not edges and $\{a, b, d, e\}, \{b, c, d, e\}, \{a, c, d, f\}$ do not form perfect matchings. However:
(1)If we move $a$ to $d$ and get $\{d, b, c\}$, ${d, b, g, e}$ forms a perfect matching $\{de, bg\}$ so neither of $d$ and $b$ could move (No.1 explicit law).
(2)If we move $b$ to $e$ to get $\{a, e, c\}$, $a$ could not move to $d$ because $de$ is an edge (No.1 explicit law). $c$ could not move to $f$ since $af$ is an edge (No.1 explicit law). $e$ could not move to $h$ as $hc$ is an edge.
(3)We could not move $c$ to $f$ as $af$ is an edge.
Then $\{a, b, c\}$ is a deadlock because of the No.2 recursive law.
For the second example $s = \{a, b, c\}$ and $\text{Next}(s) = \{d, e, f\}$. The induced bipartite graph $G[s \cup \text{Next}(s)]$ has a perfect matching so none of $a, b, c$ could move. Please note that three vehicles move one by one. If they can move simultaneously, they can move to $\{d, e, f\}$ together without an annoying deadlock.
For the third example, $\{a, b\}$ forms a deadlock. $\{a, b\}$ can only move simultaneously to $\{a_1, b_1\}, \{a_2, b_2\}, \{a_3, b_3\}$, then neither of them could move, as $\{a_4, b_3, a_5, b_4\}$ and $\{a_3, b_4, a_4, b_5\}$ have perfect matchings. If the edge $a_4b_4$ is removed, $\{a, b\}$ is not a deadlock. So a naive recursive algorithm may look many steps forward.
$\textbf{III. My attempts}$
(1) Formulate these into formal math definitions. I do some case studies into several examples.
(2) The perfect matching $s$ and $\text{Next}(s)$ is the root cause of deadlocks. Therefore, I think about a DFS algorithm similar to the Edmonds Blossom algorithm. However, the obstacle is that perfect matchings are only generators of the deadlock set, not the set itself. For example, in the third example, $\{a, b, a_1, b_1\}$ does not contain a perfect matching.
(3)I consider the $m$-radix bitmasking dynamic programming. They key idea is to reduce duplicate computations. If the algorithm has checked the state $\{a, b, c, d, e\}$ is not a deadlock, then the algorithm should not consider the edges connecting $\{b, c, d, e\}$ when checking $\{Next(a), b, c, d, e\}$. But this idea also reduces to a super long boolean expression. Shall I consider the cliques in the complement graph $\bar{G}$?
The bounty expired without answers. If you have a new idea, you can comment on this problem and I will start another bounty.
