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).


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.