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.

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

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.

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.