# Efficient algorithms to determine whether vertices form a deadlock

$$\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.

• Why is the Next operator relevant? It's defined in part I but it does not appear in the definition of a deadlock. Commented Jun 18, 2022 at 19:14
• @Misha It would be more convenient to define the next operator, however the next operator is irrelevant with the definition of a deadlock. You are right, thanks for your comments. Commented Jun 18, 2022 at 20:05
• I don't get your drawings. Is time supposed to run from left to right? Are the edges roads? Why do multiple vehicles move at once? Commented Jun 22, 2022 at 19:16
• @Christian For example, in Example2, $p_1$, $p_2$, $p_3$ are roads and vehicles move from left to right (that's why I define $s+e_i$ instead of $s-e_i$ in No.2 recursive law). Edges correspond to the geometric constraints. Some vertices are too close so that two vehicles cannot stand on these vertices simultaneously. In Example2, if three vehicles stand on $a, b, c$, then none of them can move. Because, if $a$ moves to $d$, $b$ and $d$ conflicts. If $b$ moves to $e$, $c$ and $e$ conflicts. If $c$ moves to $f$, $a$ and $f$ conflicts. Therefore, perfect matchings are harmful. Commented Jun 23, 2022 at 1:29
• It seems that the Recursive Law does not capture the situation you wish to describe in Example 3. Since the Recursive Law as it's currently stated only looks one step ahead, it only identifies (a3,b4) and (a4,b3) as deadlock states but does not identify (a,b) as a deadlock state.
– mhum
Commented Jun 23, 2022 at 23:54