2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.