<p>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.</p>

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

CC BY-SA 3.0
2017-08-25T07:01:29.253Z
2017-08-25T12:26:57.693Z
2017-08-25T12:26:57.693Z
Thomas Kalinowski
<p>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$.</p>

<p>The problem is therefore solvable in time $O(mn)$.</p>

CC BY-SA 3.0
2017-08-25T06:11:49.177Z
But there might be $k\in I$ with $b_k^j>b_i^j$.
Thomas Kalinowski
CC BY-SA 3.0
2017-08-25T07:42:59.717Z
You are right, of course.
Some Random Guy
CC BY-SA 3.0
2017-08-24T20:15:54.117Z
2017-08-24T20:15:54.117Z
Some Random Guy
<p>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.  </p>

<p>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\}$. </p>

<p>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?</p>

<p>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. </p>

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

<ds.algorithms><np-hardness>
Check the match of the maximum of each subset
Liam_math
# Check the match of the maximum of each subset

(Asked by: username_0 on 2017-08-23)

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.

**Tags:** ds.algorithms, np-hardness

---

## 2 answers

### Answer by username_1 on 2017-08-25. Score: 1

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


---

### Answer by username_2 on 2017-08-24. Score: 0

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)$.

> **Comments:**
> **username_1**: But there might be $k\in I$ with $b_k^j>b_i^j$.  
> **username_2**: You are right, of course.  

---

