# #StackBounty: #algorithms #graphs #np-complete #subsequences Polynomial time algorithm for finding a maximal monotone subset

### Bounty: 50

Input:
Some fixed $$k>1$$, vectors $$x^i,y^iinmathbb R^k$$ for $$1le ile n$$.

Output:
A subset $$Isubset{1,dots,n}$$ of maximal size such that
$$(x^i-x^j)^T(y^i-y^j) ge 0$$ for all $$i,jin 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, we search for a longest increasing subsequence of $$y^1,dots,y^n$$. Such a subsequence can be found in $$O(nlog n)$$.
• The problem is related to the notion of a monotone operator $$F:mathbb R^ktomathbb 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^2inmathbb 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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.