4
$\begingroup$

It is possible to use deep learning to give approximate solutions to NP-hard graph theory problems?

If we take, for example, the travelling salesman problem (or the dominating set problem). Let's say I have a bunch of smaller examples, where I compute the optimal values by checking all possibilities, can this be then used for bigger problems?

In particular, let's say I take a large graph and just optimize subgraphs of this large graph. This is perhaps a more general question: My experience with deep learning (TensorFlow/Keras) is to predict values. How can I get graph isomorphism and/or a list of local moves on the graph, to obtain a better solution? Can ML/DL give you a list of moves or local changes to get closed to an optimal value, or does it just return the predicted optimal value?

$\endgroup$
1

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.