Algorithmic complexity of a Maximum Capacity Representatives variant

I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can be something similar to a special instance of the Maximum Capacity Representatives problem, which is NP-complete. However, the objective function to optimize in my case is different than the one in the MCR problem.

The problem that I am trying to solve is the following:

INSTANCE: Disjoint sets $S_1, \ldots, S_m$ and, for any $i \neq j$, $x \in S_i$, and $y
\in S_j$, a nonnegative capacity $c(x,y)$.

SOLUTION: A system of representatives $T$, i.e., a set $T$ such that, for any $i$, $\vert T \cap S_i\vert=1$.

MEASURE: $\min \{c(x,y): x,y \in T \}$.

And my goal is to maximize $\min \{c(x,y): x,y \in T \}$.

Do you know any way to determine the complexity of my problem? Is there any well known problem in the literature that can be reduced to this one?,

Thanks in advance.

I'm assuming that the goal of your optimization problem is to maximize $\min \{ c(x,y) : x,y \in T \}$. The decision problem is then:


Given a system $S_1,\ldots,S_m$ of disjoint sets, a cost function $c\colon S \times S \to \mathbb{R}_+$ (where $S = S_1 \cup \cdots \cup S_m$) and a number $\gamma \in \mathbb{R}_+$, decide whether there is a choice of representatives $t_i \in S_i$ such that $c(t_i,t_j) \geq \gamma$ for all $i \neq j$.

This problem is NP-hard (and so NP-complete), by reduction from max clique. Given a graph $G = (V,E)$ and a number $m$, let $S_i = \{i\} \times V$, define $c((i,v),(j,w))$ to be 1 if $(v,w) \in E$ and 0 otherwise, and let $\gamma = 1$. The graph $G$ contains an $m$-clique if and only if the answer to your decision problem is affirmative.

StackExchange Computer Science Q#77192, answer score: 2