Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a complete $N$-partite graph $X$ with $X_n$ denoting the $n$-th vertex bin for $1 \leq n \leq N$, where we may assume that each $X_n$ has $k$ vertices for some universal constant $k$. Assume that the edges have positive real weights and also consider a real number $r \geq 0$.

A clique is a collection of $N$ vertices, one from each bin. By completeness of $X$, any two such vertices are connected by an edge. The weight of a clique is defined to be the maximal weight among all edges contained in that clique.

Given $X$ and $r$ as above, is there an efficient algorithm that answers yes if it is possible decompose $X$ into $k$ cliques so that the weight of each clique is less than or equal to $r$, and no if there is no such decomposition?

My question is similar to the one here but I am not looking to minimize the clique weight across all possible decompositions, just to confirm that there is a decomposition satisfying the upper bound of $r$.

Update: Since the problem is unfortunately NP complete (see the answer below),

Are there any known polynomial-time approximations and/or practical heuristics to attack such a problem?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

The reduction in the answer to the question you have linked to shows that your problem is NP-complete. For a complete 3-partite graph with edge weights 1 and 2 it is NP-complete to decide if there is a decomposition into triangles of weight 1 (your weight function). Actually, usually NP-completeness of an optimization problem is defined by NP-completeness of the corresponding decision problem, if there exists a solution reaching a given threshold.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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