Assume I need to solve an NP-complete problem, for which problem-specific methods (e.g. efficient heuristics or exponential algorithms faster than naive one) are not well developed. If the size of input is n, then, in theory, I could reduce the problem to SAT of size P(n), where P is some polynomial, and use SAT solvers. Or I could reduce it to other NP-complete problem with well-developed algorithms available.

Of course, I would like to use reduction with P(n) being polynomial with as low degree as possible.

1) Is there a (reasonably recent) book/survey/webpage in which I can learn what are the most efficient known reductions from some (as many as possible) NP-complete problems to (say) SAT?

2) I am sure many such reductions has already been implemented, some of them open source. Is there a webpage collecting links to such implementations?


For the reduction of the Asymmetric Traveling Salesman Problem to the Symmetric Traveling Salesman Problem two methods exist: one reduces ATSP instances to STSP instances using three nodes and a later one requires only two nodes per node of the ATSP instance; a description can be found in On Asymmetric TSP: Transformation to Symmetric TSP and Performance Bound. The reduction using two nodes is likely the most efficient possible reduction from ATSP to STSP.


Your Answer

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

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