Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk?
I have done some research and the most similar-sounding problem I have found is the longest path problem, which is in fact rather different as far as I understand it: it is not concerned with walks, but simple paths.
The first solution that pops into my mind is to:
- Label all nodes with 1.
- Find a cycle and replace it with a single node labelled with the sum of the labels of the nodes in the cycle. This newly-created node should retain all incoming and outgoing edges of the cycle it replaces (considered as a whole).
- Repeat step 2 until no cycles can be found.
- Replace each node with a chain the length of which is determined by the node's label. Retain the incoming and outgoing edges of the original node by connecting them to the beginning and the end of the chain, respectively.
- We should have a DAG at this point. A cursory Google search reveals linear time algorithms to solve the "longest path in a DAG" problem.
This sounds horribly complicated (even assuming it's correct to begin with) and I was wondering if I could leverage your expertise to improve this solution, or scrap it altogether and come up with something sensible, or even reframe the problem so that a solution is easier to find.