I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the graph. I would like to know whether the problem can be solved in polynomial time.
More details of the terms:
Complete $n$-partite graph: a graph in which vertices are adjacent if and only if they belong to different partitions (wikipedia). There are $n$ partitions in the graph. (In my case, each partition contains exactly $n$ vertices.)
Minimum weight clique: Every edge in the graph has a weight. The weight of a clique is the sum of the weights of all edges in the clique. The goal is to find a clique with the minimum weight.
Note that the size of the required clique is $n$, which is the largest clique size in a complete $n$-partite graph, and it is always attainable.
I have searched for hours and there seems no research tackling the exact problem. Any suggestions?