This question is an extension of this one.


  • $D(V, A)$ be a $k$-partite DAG;
  • $P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ be the set of partitions;
  • $c_p \in \mathbb{R}^{+}$ be the profit of partition $p$, $\forall p \in P$;
  • $A = \{ (i, j) : \forall_{1 \leqslant k \leqslant |P| - 1} (i \in p_k \wedge j \in p_{k + 1}) \}$ be the set of arcs;
  • $d_{ij}$ be the distance of arc $(i, j) \in A$; And
  • $L$ be a distance limit parameter.

For instance, consider the following DAG example.


Where the following partitions, with their respective profits, are given.

  • $p_1 = \{ 1, 2 \}$, and $c_1 = 3$;
  • $p_2 = \{ 3, 4, 5 \}$, and $c_2 = 6$;
  • $p_3 = \{ 6, 7 \}$, and $c_3 = 1$.

Note that, the number of nodes of a path $s$ in $D$ represents the number of partitions visited/covered by such path. With this insight, we state the following definition.

Definition 1. We denote as $P_s \subseteq P$ the set of partitions visited by path $s$.

For instance, for the path $s = (1, 4, 7)$ we would have as $P_s$ all the partitions in $P$, by removing the last node of $s$, and thus resulting in $s = (1, 4)$ we would have $P_s = \{ p_1, p_2 \}$.

We also state a definition for the profit of a path $s$.

Definition 2. We denote as $c_s = \sum_{p \in P_s} c_p$ the profit of path $s$.

And, we also propose some definitions for the possible paths we may have.

Definition 3. $s_{ij}$ is the shortest $i$-$j$-path in $D$.

Definition 4. $l_{ij}$ is the length of $s_{ij}$.

We aim to find the most profitable path $s$ in $D$ such that its length is limited to $L$, i.e. $\sum_{a \in A(s)} d_a \leqslant L$. Precisely, we seek for

$\max_{k, l \in \{ 1, \dots, |P| \}, i \in p_k, j \in p_l : k \leqslant l \wedge l_{ij} \leqslant L } \{ c_{s_{ij}} \}$.

A simple solution, would be by means of complete enumeration of the possible sequences of partitions we could have, and then check whether the shortest path between these two partitions is feasible, i.e. has its length less or equals than $L$.

  1. For each $k, l = 1, \dots, |P| : k \leqslant l$:
  2. If $\min_{i \in p_k, j \in p_l} l_{ij} \leqslant L$, and $\sum_{k \leqslant m \leqslant l} c_{p_m} >$ best profit attained so far, then update bet solution;
  3. End for each.

According to the algorithm given in this comment, we can calculate all the $l_{ij}$, $\forall i, j \in V$, in $\mathcal{O}(|V|^2 \kappa)$, where $\kappa = \max_{p \in P} |p|$. Therefore, the complexity of the previously presented algorithm would be $\mathcal{O}(|V|^2 \kappa + |P|^2\kappa^2)$.

My concern here is, could we speedup this task?

PS.: Note that, this problem could be represented as a Resource Constrained Longest Path Problem.

Thanks and regards.



Your Answer

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