Search code examples
algorithmgraphgraph-algorithm

Longest path in cyclic directed graph with edges that have constrained number of passes

I have a directed graph with cycles. The most important part about this graph is that every edge has a constraint of how many times it can be passed, and after that it should become "unusable".

How would I go about finding a longest path? Any info or link or comment would be appreciated. Thank you!

Solution

  • Unfortunately this problem is NP-complete, meaning it's very unlikely that there exists a "fast" algorithm (one that will solve every instance in polynomial time); you'll need to either settle for fast heuristics that don't guarantee to find an optimal solution, or use an exponential-time algorithm that will only be able to solve small instances in a reasonable time.

    I'll show this by reducing the NP-complete problem Hamiltonian Path in a Directed Graph (HP) to your problem. Briefly, the idea is: If some algorithm exists that solves every instance of your problem "quickly" (meaning in polynomial time), then it could also be used as a subroutine to solve every instance of HP -- and that seems unlikely, since no one knows how to solve HP (or any NP-complete problem) in polynomial time, despite decades of CS research.

    In HP, we are given a directed graph G = (V, E), and the task is to determine whether there is a path that visits all |V| vertices exactly once. Given an instance of this problem, we can construct an instance G' of your problem as follows:

    • Replace each vertex v with three vertices v_in, v_mid and v_out, change all in-edges to v to be in-edges to v_in, and change all out-edges from v to be out-edges from v_out; call these edges "ebony edges" (they correspond to edges in G). Also add edges from v_in to v_mid and from v_mid to v_out; call these edges "velvet edges" (they correspond to a vertex in G).
    • Assign every edge a pass limit of 1.

    There is a path of length 3|V|-1 in this graph if and only if there is a Hamiltonian Path in the original graph G:

    "If" direction: Suppose G contains a Hamiltonian Path. This corresponds to a path of length 3|V|-1 in the constructed graph that starts and ends with a pair of velvet edges, and alternates between velvet and ebony edges with the pattern VVEVVE...EVV.

    "Only if" direction: Suppose there exists a path P of length 3|V|-1 in the constructed graph. The pass limit on every edge is 1, so every edge appears at most once in this path. P must have one of the following edge patterns:

    1. VVEVVE...EVV
    2. VEVVE...EVVE
    3. EVVE...EVVEV

    In each case, P traverses at least one of the two velvet edges corresponding to each vertex in G, and so corresponds to a Hamiltonian Path in G.