# 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?,

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.
• Thanks, but I am still confused in one part. If I understand well, for this proof I don't care about the real values of the costs, I map them to be 1 or 0. However, I don't understand how to decide whether they are mapped to 1 or 0, it depends on the existence of the edge $(v,w)$, but when does $(v,w)$ exists in $E$? – Guillermo Jun 25 '17 at 5:03
• Is the value $\gamma=1$ due to the mapping of the costs, right?, I am sorry if I am having trouble with some details, this is the first time that I see the max clique problem (I am reading about it). – Guillermo Jun 25 '17 at 5:19
• You can choose any value in $(0,1]$. My choice was arbitrary. – Yuval Filmus Jun 25 '17 at 5:20