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?
Is this NP-hard: min-weight n-clique in a complete n-partite graph
complexity theory;optimization;np hard
The decision version of your problem (whether there is a clique of weight at most something) is NP-hard, by reduction from 3-SAT. Let $\varphi$ be a 3CNF formula with $m \geq 7$ clauses. We create an $m$-partite graph. Each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause, and $m-7$ dummy vertices. All edges touching a dummy vertex have weight $1$. Edges connecting two conflicting assignments also have weight $1$. Edges connecting two non-conflicting assignments have weight $0$. The graph has a clique of weight $0$ iff $\varphi$ has a satisfying assignment.We can also get a hardness of approximation result this way. Given a 3CNF formula $\varphi$ with $m \geq 7$ clauses, we create an $(m+1)$-partite graph. There is a part corresponding to each clause, which has $8$ vertices corresponding to all assignments to the clause, and $m-7$ dummy vertices. In addition, there is a part with $m+1$ special vertices. All edges touching a dummy vertex have weight $m^2$. Edges connecting two conflicting assignments also have weight $m^2$. Edges connecting two non-conflicting assignments have weight $0$. Edges connecting satisfying assignments (for clauses) and special vertices have weight $0$. Edges connecting non-satisfying assignments and special vertices have weight $1$. The minimal clique in this graph has weight equal to the minimal number of unsatisfied clauses in any assignment to $\varphi$. Therefore for every $\epsilon > 0$ it is NP-hard to decide, for $(m+1)$-partite graphs, whether the minimal clique has value $0$ or at least $(1/8-\epsilon)m$. In fact, by modifying $\epsilon$ slightly we get the same result for $m$-partite graphs.