In a complete n-partite undirected graph, each partite set has n vertices. My problem is to find a min-weight n-clique in the graph. I would like to know whether the problem can be solved in poly-n time.
More details of the terms:
Complete k-partite graph: a graph in which vertices are adjacent if and only if they belong to different partite sets (wikipedia). There are k partite sets in the graph. In my problem, k = n.
Clique: A clique in a graph G is a complete subgraph of G; that is, it is a subset S of the vertices such that every two vertices in S are connected by an edge in G (wikipedia).
Min-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?
Yes, it's NP-hard via this reduction from CLIQUE.
Let (G, k) be the instance of CLIQUE (determine whether there exists a clique of cardinality at least k). Prepare a k-partite graph H with k copies of each vertex in G and edges between two vertices v and w if and only if they are in different parts and they are copies of adjacent vertices in G. There exists a k-clique in G if and only if there exists a k-clique in H. (With weights: make the existing edges weight 1 and introduce the missing ones with weight 0.)
(Surely this is in the literature, but it's Sunday, and I don't feel like looking.)