Is this NP optimization?

Question

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?

Answer 1

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.)

Answer 2

Quadratic assignment can be easily reduced to this problem by associating a location with each bipartite set and a facility with each vertex of each bipartite set. The weight of any edge between two vertices that are associated with the same facility is set to infinity. Since quadratic assignment is NP-hard, then this problem is NP-hard as well.