1
$\begingroup$

Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the weights in nodes)?

I assume that since the decision counterparts of both problems are NP-complete, and all NP-complete can be transformed to each other, there must be a way to transform their functional counterparts as well, although I don't know whether that assumption is in general true.

I have already found a way to transform a maximum weighted clique problem (if the graph is connected) to a multidimensional 0-1 knapsack by creating a variable and a restriction for each (undirected) pair, but I cannot think a way to do the inverse transformation, because the knapsack problem doesn't have a "transitive" property, in the sense that if items a and b fit together, and b and c fit together, and a and c fit together, doesn't mean that all three fit together at once, while the clique problem does indeed have this "transitive" property (if three nodes are connected to each other two-by-two, a solution containing all three is feasible).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.