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?
Asked By : linusz
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13135
0 comments:
Post a Comment
Let us know your responses and feedback