**Input:**
Some fixed $k>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<\dots<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 maximal 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.