7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – STanja Oct 3 at 19:28
  • $\begingroup$ 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". $\endgroup$ – Klaas Oct 3 at 19:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Dmitry Oct 3 at 21:49
  • $\begingroup$ 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? $\endgroup$ – Klaas Oct 4 at 10:39
  • $\begingroup$ 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. $\endgroup$ – Zachary Vance Oct 7 at 19:29
0
$\begingroup$

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$

I'd suggest checking if this can be reduced to the longest common subsequence problem (I suspect no, because of the lack of ordering) or to/from some form of linear programming.

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.