3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Kaya
    Commented Jul 7, 2013 at 18:52

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ why "each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause"? $\endgroup$
    – linusz
    Commented Jul 9, 2013 at 4:24
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2013 at 21:23
  • $\begingroup$ 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$? $\endgroup$
    – linusz
    Commented Jul 10, 2013 at 5:26
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Jul 10, 2013 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.