# Polynomial time algorithm for finding a maximal monotone subset

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

• Do you want a maximal clique, or a maximum clique? In the former, we essentially cannot extend a clique to a bigger clique, which is easily found: choose an arbitrary vertex and add as many adjacent vertices such that you maintain a clique. Finding a maximum clique is $\mathsf{NP}$-complete because we are looking for the largest clique out of all possible cliques. – STanja Oct 3 at 19:28
• You are right, the wording of the remark was ambigous. I have now edited it to say "maximum" instead of "maximal". However, I think the problem statement was precise: We search a subst I "of maximal size". – Klaas Oct 3 at 19:41
• Just a small comment: if $k$ can depend on $n$, then it's NP-hard, since we can build a reduction from maximum clique: $k = n^2$, and $i * n + j$-th coordinate is $0$ for all vertices except $i$ and $j$. If there is an edge between them, then the coordinate is $0$ for both; otherwise, it's $1$ fr one and $-1$ for another. – Dmitry Oct 3 at 21:49
• That's correct, I also thought about adding this as a further remark :-) Maybe asking the following question can lead to some insights: Let's suppose $k=2$. Can all possible graphs (i. e. all possible sets $E$) be realized by choosing $x_i, y_i$ appropriately? If not, what are the obstructions? – Klaas Oct 4 at 10:39
• If you want k to be fixed, traditionally it shouldn't be listed as an input. It should instead be a fixed parameter of the problem. I might remove it from your list of inputs for clarity. – Zachary Vance Oct 7 at 19:29

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$$
To nitpick here, coordinates should really be taken from $$\mathbb Z$$ bounded by some reasonable (say, polynomial) function for CS problems, not "$$\mathbb R$$". 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.