# Non-dominated maximal paths in a DAG

Let $$D(V, A)$$ be a DAG. We call a dominated path in $$D$$ a path $$P$$ such that

$$P$$ is maximal and $$\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$$

that is, $$P$$ is a dominated path iff $$P$$ is maximal and there exists another path $$P^{'}$$, also maximal, containing all the nodes of $$P$$, along with at least one additional node. If such path $$P^{'}$$ doesn't exist, we say that $$P$$ is a non-dominated path. For instance, let's take the below example:

The paths:

• $$(1, 5)$$ is a dominated;
• $$(1, 6, 5)$$ is a non-dominated;
• $$(1, 2, 4, 5)$$ is a dominated; And
• $$(1, 2, 3, 4, 5)$$ is a non-dominated.

My question is, how can we find all the non-dominated paths? Obviously, a straightforward solution would be to enumerate all maximal paths in $$D$$, and apply a dominance check to each retrieved path. However, I am trying to find a more efficient way of doing so, even if no "polynomiality" is possible.

• Minor note: There can be exponentially many non-dominated paths, so in the worst case, any algorithm might have to take exponential time.
– D.W.
Commented Jan 3 at 21:59
• Thanks for the observation. Yes, you are right. I was expecting this. However, the steps in the answer guarantee that any maximal path of the resulting graph will be a non-dominated one, which automaticaly removes the "wrong" options. Commented Jan 4 at 23:21

After some hours of paper sketching, I think I could come up with somethig.

Let $$P = (v_1, \dots, v_n)$$ be a path in $$D$$. Then we have

Lemma 0: Any other permutation of $$P$$ results in an invalid path for $$D$$.

Proof: The replacement of $$v_{j}$$ by $$v_{k}$$ in $$P$$, such that $$j < k$$, resulting in the following permutation $$(v_1, \dots, v_k, \dots, v_j, \dots, v_n)$$, implies that the paths from $$v_j$$ to $$v_k$$ (as $$P$$ indicates), and from $$v_k$$ to $$v_j$$ (as the new permutation shows), exist simultaneously. What gives a contradition, since $$D$$ is a DAG.

Let $$S_{k} = (v_k, \dots, v_{k + 1})$$ be a path between $$v_k$$ and $$v_{k + 1}$$ in $$D$$, $$\forall k \in \{1, \dots, n - 1\}$$. Then

Lemma 1: $$(v_1, \dots, v_{k-1}) \cap S_{k} = \emptyset$$

Proof: If there exists a node $$v_m \in (v_1, \dots, v_{k-1}) \cap S_{k}$$, then there exists, simultaneously, paths from $$v_k$$ to $$v_m$$, and from $$v_m$$ to $$v_k$$, which forms a cycle. Thus, a contradiction, given the DAG property of $$D$$.

Lemma 2: $$(v_{k + 2}, \dots, v_{n}) \cap S_{k} = \emptyset$$

Proof: Same reasoning as above.

Corollary 1: Path $$P^{'}$$ dominates $$P$$ iff. $$\exists_{k \in \{1,\dots,n - 1\}} (|S_k| > 2 \wedge P^{'} = (v_1,\dots,v_k)\cup (S_k \backslash \{v_k, v_{k + 1} \}) \cup (v_{k + 1}, \dots, v_n))$$.

Proof: This is a consequence of Lemmas 0, 1, and 2. Because,

1. According to Lemma 0, any path $$P^{'}$$ dominating $$P$$ would have to maintain the order of the nodes in the permutation given by $$P$$;
2. According to Lemmas 1 and 2, any node inside $$S_k$$ (disregarding the endings), cannot belong to the dominated path $$P$$;
3. Therefore, the only possible expansion for $$P$$, is to find a $$S_k : |S_k| > 2$$ and to append it accordingly in $$P$$, resulting in a $$P^{'}$$.

For instance, in the picture given above, we have that

$$P^{'} = (1, 2, 3, 4, 5)$$ dominates $$P = (1, 2, 4, 5)$$, since the extract $$(2, 3, 4)$$ can be appended to $$P$$. The same is valid for $$(1, 6, 5)$$ and $$(1, 5)$$.

Corollary 2: A path $$P^{'} = (v_1, \dots, v_n)$$ is a non-dominated path iff. $$\nexists_{k \in \{1,\dots,n-1\}} (|S_k| > 2)$$ and $$P^{'}$$ is maximal.

Proof: This is a consequence of Corollary 1.

Let $$D_R$$ be the transitive reduction of $$D$$, then:

Corollary 3: $$P^{'}$$ is a path in $$D_R$$ iff. $$\nexists_{k \in \{1,\dots,n-1\}} (|S_k| > 2)$$.

Proof: This is a consequence of the definition of transitive reduction.

Theorem 0: $$P^{'}$$ is non-dominated iff. $$P^{'}$$ is a maximal path in $$D_R$$.

Proof: Every arc of $$P^{'}$$ belongs to $$D_R$$.

Please, feel free to suggest and point corrections.