1
$\begingroup$

Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number.

Question: determine whether, for all subset $I\subseteq \{1, \cdots, n\}$, there is some $T_j$ ($1\leq j\leq m$) such that $\max\{a_i\mid i\in I\}=\max\{b_i^j\mid i\in I\}$.

Obviously there is an exponential time algorithm to do this (one can just enumerate all $I$), but can we do better to have a polynomial-time algorithm? or is it NP-hard?

Example: $S=(1,2,0)$, $T_1=(2,1,0)$, $T_2=(2,0,1)$, $T_3=(1,0,2)$, $T_4=(0,2,1)$ gives an affirmtive answer.

Motivation: this question is from database research, the background of which is a bit hard to describe precisely here.

$\endgroup$
1
$\begingroup$

You can do the following. For every $i\in\{1,\dotsc,n\}$, start with the set $I=\{k\,:\,a_k\leqslant a_i\}$. Let $K=\{k\,:\,\exists j\ b_k^j=\max\{b^j_\ell\,:\,\ell\in I\}=a_i\}$. If $K=\emptyset$, then $I$ is a counterexample. If $i\in K$ then there is no counterexample with $i\in I$ and $a_i=\max\{a_k\,:\,k\in I\}$. If $K\neq\emptyset$ and $i\not\in K$ then any counterexample $J$ with $i\in J$ and $a_i=\max\{a_k\,:\,k\in J\}$ will be a subset of $I\setminus K$. So we can replace $I$ by $I\setminus K$, and iterate.

It is necessary and sufficient that for every $i$ we end up with $i\in K$.

$\endgroup$
0
$\begingroup$

It is obviously necessary that for every $i \in \{1,\ldots,n\}$ there is a $j$ such that $a_i = b_i^j$ because we can choose $I = \{i\}$. But this is also a sufficient condition: Given a set $I$, let $i$ be the index in $I$ such that $a_i$ is maximal. Then the corresponding $j$ satisfies the condition $a_i = b_i^j$.

The problem is therefore solvable in time $O(mn)$.

$\endgroup$
  • $\begingroup$ But there might be $k\in I$ with $b_k^j>b_i^j$. $\endgroup$ – Thomas Kalinowski Aug 25 '17 at 6:11
  • $\begingroup$ You are right, of course. $\endgroup$ – Some Random Guy Aug 25 '17 at 7:42

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.