I have a problem with the following equivalent formulation in graph theory:
Take $G(V, E, W)$ a complete weighted graph, where $w_{ij} > 0$ is the weight of edge $e_{ij}$. For a given $k$, find the clique $Q$ with $k$ vertices, such that its minimum edge weight is maximized over the graph.
$$Q = \text{argmax}_{I} \min_{i,j \in I} w_{i,j}\\ \text{such that } |I| = k$$
I have seen similar problems such as finding cliques where the sum of weights are maximized, but not a maxmin problem like above. I have also found the following paper [1], which addresses a similar problem, but again different than what I have here.
Based on what I have seen in similar problems, I suspect that this problem is also NP-hard. I was wondering if this is the case, and whether anyone knows an approximation to this problem.
[1] T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science, 38(2-3):293-306, 1985.
This problem is easy and can be solved by the following algorithm. Remove all the edges from the graph and order them with respect to its weight, from the biggest to the smallest. Then reinsert the edges of the graph consecutively with respect to the order (if several edges have the same weight then we reinsert them simultaneously). A first $k$-clique appeared in the graph will be the required $\operatorname{argmax}$.