Polynomial time algorithm for finding a maximal monotone subset Input:
Some fixed $k&gt;1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
Question:
Can this be computed in polynomial time in $n$?
Remarks:

For $k=1$ this is equivalent to the problem of finding a longest increasing subsequence. Indeed, assuming that $x_1&lt;\dots&lt;x_n$, we search for a longest increasing subsequence of $y_1,\dots,y_n$. Such a subsequence can be found in $O(n\log n)$.
The problem is related to the notion of a monotone operator $F:\mathbb R^k\to\mathbb R^k$. Monotonicity of $F$ means that $(x_1-x_2)^T(F(x_1)-F(x_2))\ge 0$ for all $x_1,x_2\in\mathbb R^k$.
The problem can be formulated as a search for a maximum clique in the graph $G=(V,E)$ with vertices $V=\{1,\dots,n\}$ and edges
$E = \{(i,j) \;:\; (x_i-x_j)^T(y_i-y_j)\ge 0 \}$.
The general clique problem is NP-complete.
However, it might be possible to exploit the special structure of $E$ (as shown in the first remark, this is possible when $k=1$).

I would appreciate any hint or comment on this problem.
I stared at this a while now with $k=2$ and got nowhere.

Let's take on $k=2$. To avoid confusion with x and y coordinates, I'll call the vectors $a_i, b_i$ instead.
Lets define $D(i,j)=(a_j-a_i)^T(b_j-b_i) \ge 0$, and $R(i,j)$ to be the boolean relation which holds when $D(i,j)\ge0$.
For $k=1$, R was a total ordering, which is what let us find increasing subsequences. For $k=2$, it's not even a partial ordering, which makes me think any solution will not resemble the $k=1$ case.

Take $x_1,x_2,x_3=(0,0),(0,1),(1,0)$; $y_1, y_2, y_3=(0,0), (-6, 1), (-5,-5)$
$V(1,2)=1$; $V(2,3)=1$; $V(1,3)=-10$



I'd suggest checking if this can be reduced to the longest common subsequence problem (I suspect no, because of the lack of ordering) or to/from some form of linear programming.
To nitpick here, coordinates should really be taken from $\mathbb Z$ bounded by some reasonable (say, polynomial) function for CS problems, not &quot;$\mathbb R$&quot;. I suspect you can show it's NP-complete otherwise, say by reduction to the longest common subsequence problem, but in some way that's not really related to whatever your real problem is. That said, I didn't succeed at actually doing so.