Feasibility of equations with max constraints

Question

Relating to a question I posted here, I have formulated the following question:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$.

How to check the following system of equations is feasible? Assumption: $x_i, b_k$ are all in $[0,1]$

$\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

for example:

$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of this problem? Obviously it is in NP, but is it NP-hard? It would be a surprise if such an easy problem does not have a polynomial algorithm. Does linear programming help here?

Many thanks.

Answer 1

Let $y_i=\min\{b_k| i\in J_k\}$. Observe for any feasible solution, $x_i\leq y_i$.

Claim: The system of $\max$ equations is feasible iff $x_i=y_i$ for $1\leq i\leq n$ is a solution.

Proof. If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible

Consider any solution, and $x_i < y_i$ for some $i$. We can increase $x_i$ to $y_i$ without violate any equation. Assume it violates the $k$th equation, namely $\max\{x_j|j,i\in J_k\}=b_k$, then it implies $y_i = \max\{x_j|j,i\in J_k\} > b_k$, but that's a contradiction because $$ b_k \geq \min\{b_j| i\in J_j\} = y_i = \max\{x_j|j,i\in J_k\} > b_k $$.

The algorithm is just compute $y_i$s and check if it satisfies all the equations. This takes linear time.