2
$\begingroup$

I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there's better terminology, then please let me know about this.

It's important that I'm able to determine what the path is, so I would need an algorithm that can produce a list of edges.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Can you state your problem in clear terms? What is the input, and what is the required output? Try to be exact and provide all details. $\endgroup$ – Yuval Filmus Mar 21 '20 at 9:14
  • 1
    $\begingroup$ In particular it is important to know if you're looking for a simple path (i.e., no repeated vertices) and if your input graph is a DAG. $\endgroup$ – Steven Mar 21 '20 at 12:59
  • $\begingroup$ Can the path use a vertex more than once? Can it use an edge more than once? $\endgroup$ – D.W.♦ Mar 21 '20 at 16:23
  • $\begingroup$ Thanks everyone, I've provided some clarifications. $\endgroup$ – JasTonAChair Mar 22 '20 at 3:57
  • $\begingroup$ This problem is unfortunately NP-Hard (it's basically the Hamiltonian Path problem), so solving it exactly will take a long time unless the input graph is pretty small. $\endgroup$ – j_random_hacker Mar 22 '20 at 13:02
2
$\begingroup$

The problem you are defining is called Longest Path (and occasionally Longest $s$-$t$-Path) and is NP-complete.

That is, there is an algorithm for solving it, but you shouldn't keep you hopes up when it comes to the running time of the algorithm: it's unlikely to run in polynomial time.

The trivial algorithm is to check for every permutation of the graph, in time $O(d! \cdot 2^{dn})$, but this becomes intractable extremely quickly. It is possible to bring this down to $O(2^n \cdot \text{poly}(n))$.

You have three options as far as I can see it:

  • limit the length of the path you need to some reasonable integer $k$ and solve with FPT techniques
  • use an approximation algorithm
  • limit the type of input graph to certain smaller and easier graph classes.

Note 1: As Yuval Filmus points out, the problem Longest Path is usually referring to the undirected version. However, the problem remains NP-complete also in its directed version by a reduction from Directed Hamiltonian Path (Between Two Vertices) (Garey & Johnson, 1979).

Note 2: Yuval Filmus also pointed out that it is solvable in single-exponential time.

Note 3: The problem is solvable in linear time on DAGs, and if you allow repeating edges, the answer is always infinite when your graph has a cycle.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for those details. Does this answer consider the possibility to write logic to avoid traversing an edge or vertex more than once? I think that would mean that each traversal, in effect, is dealing with a DAG. Does my logic there make sense? $\endgroup$ – JasTonAChair Mar 23 '20 at 0:16
  • $\begingroup$ I answered that comment in Note 3. The problem is linear time solvable in DAGs. $\endgroup$ – Pål GD Mar 23 '20 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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