4
$\begingroup$

Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition.

SP-Graph

I have a graph dataset that is of this type, and I have to enumerate all paths in the series-parallel graphs. Are there any existed algorithms? If so, what is the time complexity of it?

$\endgroup$
  • $\begingroup$ @Juho List them all. Not only just count the number of paths. $\endgroup$ – Kevin Dong Jun 23 '19 at 15:17
  • 1
    $\begingroup$ The number of such paths is exponential in the size of the graph, so even generating all the output takes a lot of time. $\endgroup$ – Juho Jun 23 '19 at 15:21
  • $\begingroup$ @Juno You're right. It may take a long time to perform this task. I am also curious about the space complexity of that possible existed algorithm. $\endgroup$ – Kevin Dong Jun 23 '19 at 15:32
3
$\begingroup$

Treat SPG as DAG

We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move "up". This phenomenon can be proved easily by structural induction.

So we can view a SPG as a directed acyclic graph (DAG) naturally, where every edge is assigned the direction such that its head is nearer to the sink than its tail. For the SPGs in the illustration of the question, the head of an edge is lower than its tail.

Many Algorithms for DAG

There have been many algorithms that lists all paths from a source node to a destination node in a DAG such as this one and this one.

Time-complexity and space-complexity

For simplicity, assume the given SPG is a simple graph. (The case of multi-graph is not much different.) We have $|E|\le2|V|-3$. This inequality will not be used here; it is shown just to illustrate an SPG is a relatively simpler graph.

What is the maximum number of paths from source to sink in an SPG of $n$ vertices?

A rough estimate is $2^{\Omega(n)}$. In fact, we can show that the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, which is $\Theta(4^{n/5})$. So the worst time-complexity for all algorithms is about $\Omega(n4^{n/5})$.

If the algorithm stores that all paths in full detail before outputting anything or if the space used by output is counted towards usages, then the space-complexity is $O(n4^{n/5}$). However, if the space used by output is not counted towards space-complexity, the space-complexity can be reduced to $O(n)$ if we use a depth-first search such as the following code in Python, assuming the adjacency list of the SPG is given in the input.

def list_paths(g, path):
    children = g[path[-1]]
    if len(children) == 0:
        print(path)
    else:
        for node in children:
            path.append(node)
            list_paths(g, path)
            path.pop()


""" 
Output all maximal paths from source in O(n)-working-space-complexity.
The parameter g is assumed to be an adjacency list that represents a valid DAG. 
"""


def list_all_paths(g, source):
    list_paths(g, [source])


g = {1: [2, 3],
     2: [4, 5, 6],
     4: [7],
     5: [7],
     6: [7],
     7: [8],
     3: [8],
     8: [9],
     9: [10, 11],
     10: [12],
     11: [13],
     12: [14],
     13: [14],
     14: [],
     }

list_all_paths(g, 1)

""" Expected Output
[1, 2, 4, 7, 8, 9, 10, 12, 14]
[1, 2, 4, 7, 8, 9, 11, 13, 14]
[1, 2, 5, 7, 8, 9, 10, 12, 14]
[1, 2, 5, 7, 8, 9, 11, 13, 14]
[1, 2, 6, 7, 8, 9, 10, 12, 14]
[1, 2, 6, 7, 8, 9, 11, 13, 14]
[1, 3, 8, 9, 10, 12, 14]
[1, 3, 8, 9, 11, 13, 14]
"""

By the way, the number of all paths can be computed directly in $O(n)$ time and $O(n)$ space by either recursive dynamic programming or iterative dynamic programming following a topological sort.


Exercise 1. Show the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, where $\%$ is the remainder operator. (For $n=12$, the maximum number is $4\times5=20$)

Exercise 2. Verify the algorithm above in Python still works if the given DAG g is not a simple graph, i.e., that might be parallel edges. What is its time-complexity and working-space-complexity when $g$ is a SPG that is not necessarily a simple graph?

$\endgroup$

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.