3
$\begingroup$

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:

  1. Label all nodes with 1.
  2. 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).
  3. Repeat step 2 until no cycles can be found.
  4. 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.
  5. 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you clarify what you mean by a walk and give a definition? According to the usual definition, your problem seems to reduce to finding a maximum weight walk in the graph of the strongly connected components of the original graph. The latter is a DAG, so that is easy. $\endgroup$
    – Discrete lizard ♦
    Aug 25, 2021 at 8:45
  • $\begingroup$ Hi @Discretelizard, for walk I mean a finite or even infinite sequence of nodes connected by edges, where nodes and edges can be traversed more than once. $\endgroup$
    – gd1
    Aug 25, 2021 at 8:50
  • 1
    $\begingroup$ If you can traverse nodes and edges arbitrarily many times, then this is polynomial time solvable (the SCC-graph is a DAG). $\endgroup$
    – Pål GD
    Aug 25, 2021 at 8:52
  • $\begingroup$ I guess the crux of the matter here is that up until 30 seconds ago I didn't know what a SSC-graph was. I'll look into that. $\endgroup$
    – gd1
    Aug 25, 2021 at 8:53

1 Answer 1

Reset to default
3
$\begingroup$

The problem you have is the following: You have a directed graph and you are allowed to visit the same vertices and edges many times over. You want to find a walk starting in a vertex $s$ that visits as many vertices as possible.

First observation is that in a strongly connected component (SCC), you can visit every vertex in that SCC as many times you want.

Second observation is that if you create the "meta-graph" where each SCC is a weighted node (the weight is the number of vertices in the SCC in the original graph), then you have a DAG (this is an exercise to prove).

Third observation, which the OP pointed out, is that the problem is polynomially solvable in a DAG (it is also polytime in weighted DAGs).

The algorithm then becomes:

  1. Construct the SCC-DAG
  2. Run the (weighted version) of the polytime algorithm for DAGs.
Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 Thanks, up until minutes ago I didn't know what a SSC-DAG was. I think my algorithm would have worked in the end but in a stupidly inefficient and overcomplicated way, because the problem wasn't framed correctly. $\endgroup$
    – gd1
    Aug 25, 2021 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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