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.

| cite | improve this answer | |
  • $\begingroup$ 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$? $\endgroup$ – Guillermo Jun 25 '17 at 5:03
  • $\begingroup$ The input to the max clique problem is a graph and an integer. A graph is a list of vertices and edges. Given two vertices, you can use the list to decide whether two vertices are connected. $\endgroup$ – Yuval Filmus Jun 25 '17 at 5:04
  • $\begingroup$ 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). $\endgroup$ – Guillermo Jun 25 '17 at 5:19
  • $\begingroup$ You can choose any value in $(0,1]$. My choice was arbitrary. $\endgroup$ – Yuval Filmus Jun 25 '17 at 5:20
  • $\begingroup$ Ok, Thank you so much Yuval, you were very helpful. I think I can get the rest of the details by myself. $\endgroup$ – Guillermo Jun 25 '17 at 5:24

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.