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?


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.