Maximum number of points that two paths can reach

Question

Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, y_j)$ if $x_i \le x_j$ and $y_i \le y_j$. The question is: given these $n$ points, what is the maximum number of points that we can reach if we are allowed to draw two paths that connect points using the above rule? Paths must start from the origin and may contain repeated points. $(0, 0)$ is of course not included in the points reached.

An example: given $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$, the answer is $8$ since we can take $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ and $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$.

If we are allowed to draw only one path, I can easily solve the question by dynamic programming that runs in $O(n^2)$. I first sort the points by decreasing $x_i+y_i$. Let $D[i]$ be the maximum number of coins that one can pick up from coins $1$ to $i$ in the sorted list. Then $D[1] = 1$ and $D[i] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$. The answer then is just $\max\limits_{1\le i \le n} D[i] + 1$.

But I cannot come up with a recurrence relation for two paths. If anyone has any idea about such a recurrence relation, I would be happy to hear what they are.

Answer 1

The problem, restated and generalized: given a finite set $S$ equipped with a partial order $\le$, find chains $C_1, C_2 \subseteq S$ maximizing $\lvert C_1 \cup C_2 \rvert$. The question is about the case where $S \subseteq \mathbb R_+^2$ and $(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$.

Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$\bigl((0,0),(0,0)\bigr) < \bigl((1,0),(0,0)\bigr) < \bigl((2,0),(0,0)\bigr) < \bigl((2,0),(1,0)\bigr),$$ so this notion of best does not have optimal substructure.

Instead, we look for chains in the set $T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement.

Lemma 1 (no retracing). Let $C \subseteq T$ be a chain and define $C_1 := \{x \mid (x, y) \in C\}$ and $C_2 := \{y \mid (x, y) \in C\}$. For all $z \in S$, we have $z \in C_1 \cap C_2$ if and only if $(z, z) \in C$.

Proof. The if direction is trivial. In the only if direction, for all $z \in C_1 \cap C_2$, there exist $x, y \in S$ such that $(x, z), (z, y) \in C$. Since $C$ is a chain, $(x, z) \le (z, y) \vee (z, y) \le (x, z)$. Assume symmetrically that $(x, z) \le (z, y)$, which implies that $x \le z \le y$. We know by the definition of $T$ that $x \nless z \wedge z \nless y$, so $x = z = y$, and $(z, z) \in C$.

Lemma 2 (existence of restricted best chain). For all chains $C_1, C_2 \subseteq S$, there exists a chain $C \subseteq T$ such that $C_1 \subseteq \{x \mid (x, y) \in C\} \subseteq C_1 \cup C_2$ and $C_2 \subseteq \{y \mid (x, y) \in C\} \subseteq C_1 \cup C_2$.

Proof (revised). We give an algorithm to construct $C$. For convenience, define sentinels $\bot, \top$ such that $\bot < x < \top$ for all $x \in S$. Let $C_1' := C_1 \cup \{\top\}$ and $C_2' := C_2 \cup \{\top\}$.

1. Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.

2. Let $x'$ be the next element of $C_1$, that is, $x' := \inf \{z \mid z \in C_1' \wedge x < z\}$. Let $y'$ be the next element of $C_2$, that is, $y' := \inf \{w \mid w \in C_2' \wedge y < w\}$.

3. If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.

4. If $y < x' < y'$, set $(x, y) := (x', x')$ and go to step 9.

5. If $y \nless x' < y'$, set $x := x'$ and go to step 9. Note that $x < x' \wedge x \nless y$ implies that $x' \nless y$.

6. If $x < y' < x'$, set $(x, y) := (y', y')$ and go to step 9.

7. If $x \nless y' < x'$, set $y := y'$ and go to step 9. Note that $y < y' \wedge y \nless x$ implies that $y' \nless x$.

8. This step is never reached, as the conditions for steps 3–7 are exhaustive.

9. If $x \ne \top$ (equivalently, $y \ne \top$), set $C := C \cup \{(x, y)\}$ and go to step 2.

Dynamic Program. For all $(x, y) \in T$, compute $$ D[x, y] := \sup\biggl(\Bigl\{D[z, w] + [x \ne z] + [y \ne w] - [x = y] \mathrel{\Bigl|\Bigr.} (z, w) \in T \wedge (z, w) < (x, y)\Bigr\} \cup \bigl\{2 - [x = y]\bigr\}\biggr), $$ where $[\textit{condition}] = 1$ if $\textit{condition}$ is true and $[\textit{condition}] = 0$ if $\textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.

Answer 2

Let $P = p_1\dots p_n$ to sorted list of points.

---

Following your recurrence for one path, the first thing to note is that you have to keep track of which points have been visited by the paths; otherwise you can not count correctly. The second thing is that you have now four possibilities for every point: neither path may use it, one of them or both. So, we have to find maximising combinations for all three cases.

Formally, let $d : [0\dots n] \to (2^{[n]} \times 2^{[n]})^3$ with $d(i)$ the pair of (sets of) visited nodes of the two paths that maximise the number of visited points from the input set up to the $i$th one, with the first component the maximising pair of paths for which the first one uses $p_i$, the second component similar for the second path and the third component with both paths using $p_i$. $d$ is given by the recurrence

$\quad \displaystyle \begin{align} d(0) &= ((\emptyset, \emptyset),(\emptyset, \emptyset),(\emptyset, \emptyset)) \\ d(i) &= (\ \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R})_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L} \times \mathcal{R}')_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R}')_i} |L \cup R| \ ) \\ \end{align}$

with

$\quad \displaystyle (\mathcal{L}' \times \mathcal{R})_i = \left\{ (L \cup \{i\}, R) \mid (L,R) \in \bigcup_{j=0}^{i-1} d(j), x_i \geq \max_{j \in L} x_j, y_i \geq \max_{j \in L} y_j \right\}$,

$(\mathcal{L}' \times \mathcal{R})_i$ similar with extending $R$ and $(\mathcal{L}' \times \mathcal{R}')_i$ similar with extending both $L$ and $R$.

Needless to say, this is not very nice. This is because the problem does not lend itself to dynamic programming very well: you can not combine many partial solutions because there is no nice total ordering on the points, and you can not discard intermediate results for the same reason.

---

A nicer view on the problem is to model the set of points as weighted directed acyclic graph $G = (V, E, w)$ with

• $V = \{(0,0), p_1, \dots, p_n, (X,Y)\}$ with $X = \max x_i$, $Y = \max y_i$, and
• $E = \{ ((x_1, y_1),(x_2,y_2)) \in V^2 \mid x_i \leq x_j, y_i \leq y_j\}$ and
• $w(v_1,v_2) = \begin{cases} 0 &, v_2 = (X,Y) \\ 1 &, \text{ else}\end{cases}$.

Note that you can keep the graph smaller if you remove redundant edges, that is remove $(v_1,v_2)$ if there is a path $(v_1,\dots,v_2)$, because taking such "shortcuts" is never better advantageous.

For one path, the solution is clearly the length of the longest path $P^*$ from $(0,0)$ to $(X,Y)$. Now, if we change $w$ so that all edges leading to points on $P^*$ also have weight $0$ and compute the longest path in this modified graph, we get a path $P^+$ so that $P^*$ and $P^+$ together cover as many points as two paths can. This leaves us with a runtime in $O(|V| + |E|) \subseteq O(n^2)$ (see here).