#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<dots<x^n$, 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!!!

Leave a Reply

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