# Is this NP-hard: min-weight n-clique in a complete n-partite graph

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?

• Arbitrarily order the partitions and the vertices in them so that each vertex has a label of the form $v_{i,j}$ it is the $j^{th}$ vertex of the $i^{th}$ partition. A clique is then represented as a function from $f:{1,...,n}\rightarrow{1,...,n}$ where $f(i)=j$ implies that $v_{i,j}$ is in the clique. There are $n^{n}$ such functions. – Kaya Jul 7 '13 at 18:52

## 1 Answer

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.

• why "each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause"? – linusz Jul 9 '13 at 4:24
• That's the way I define the reduction. You can define the reduction however you want. I define the reduction this way because it works. – Yuval Filmus Jul 9 '13 at 21:23
• I don't understand why in a general 3CNF, each clause has exactly $7$ variable assignments that satisfy the clause. So it's reduction from a special case of 3SAT? Or should it be 'at most' $7$, because $7$ $=$ $2^3-1$? – linusz Jul 10 '13 at 5:26
• Let's take the clause $a \lor b \lor c$. It has three satisfying assignments for the variables $a,b,c$. If the clause is narrower than there are fewer, and as you say the construction works just as well. – Yuval Filmus Jul 10 '13 at 6:45