2
$\begingroup$

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:

DAG 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.

$\endgroup$
2
  • 2
    $\begingroup$ Minor note: There can be exponentially many non-dominated paths, so in the worst case, any algorithm might have to take exponential time. $\endgroup$
    – D.W.
    Jan 3 at 21:59
  • $\begingroup$ 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. $\endgroup$ Jan 4 at 23:21

1 Answer 1

1
$\begingroup$

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

enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.