0
$\begingroup$

Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly once before returning to the starting node. Your goal is to take the route that has the smallest sum of edge weights possible.

How could you map this problem to the maximum clique problem (searching for the largest clique in an unweighted graph) or the weighted maximum clique problem (searching for the clique that has the highest sum of node weights in a graph with node weights)?

I think mapping the TSP problem to a weighted maximum clique problem should be possible, but I am not sure how to do it. I did some research but couldn't find anything useful for this problem. Thank you in avance!

$\endgroup$

1 Answer 1

2
$\begingroup$

TSP is reducible to SAT which is reducible to 3SAT which is reducible to CLIQUE.

The reduction is not pretty, but still, it exists.

$\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.