# Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time?

There are two common ways to define a series-parallel graph (or 2-terminal series-parallel graph).

Definition 1

• repeatedly join two smaller 2-terminal s/p graphs either in series or in parallel

Definition 2

• repeatedly replace a single edge by two in series or two in parallel

A "decomposition tree" for an s/p graph shows how it is constructed according to Definition 1; each node of the tree is a s/p graph and the children of each node are the components from which that graph was built by series or parallel composition.

It is well known that a series-parallel graph can be recognized in linear time; the usual reference to this is Valdes, Tarjan and Lawler (Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. The recognition of series parallel digraphs. SIAM J. Comput. 11 (1982), no. 2, 298--313.)

It is also frequently stated in the literature that the decomposition tree can be found in linear time, either just as an assertion or with a reference to the same Valdes/Tarjan/Lawler paper.

However, when you actually read Valdes, Tarjan and Lawler, they do not construct the decomposition tree in linear time, but rather they run "Definition 2" in reverse and work on reducing the graph to a single edge by series and parallel reductions. So they recognize that the graph is s/p but they do not actually give the decomposition tree.

Does anyone know if there is an explicit reference in the literature to actually constructing the sp-tree for a series-parallel graph in linear time?

-
You can emphasize using markdown; in particular, you can use italics by sandwiching your text between underscores, like this, and you don't need to use caps (which are often interpreted as yelling). –  Qiaochu Yuan Jul 22 '10 at 8:48
Thanks, I have fixed the yelling –  Gordon Royle Jul 22 '10 at 13:05

It is easy enough to build the tree from a definition 2 description. Here is a sketch:

Suppose that SP graph $G$ occurs from subdividing graph $G'$ at an edge $e$, either in series or in parallel. Recursively, let $T'$ be the tree for $G'$. Then $e$ is a leaf of $T'$. Add two children below that leaf. Mark the node $e$ as either series or parallel according to whether the subdivision of $e$ was series or parallel.

I don't know what the efficiency of this is; it probably depends on your precise implementation of trees. And I don't know any references in the literature.

-
Yes, this is the basic idea of the algorithms that have been published over the last few decades. The tricky part is how to do this efficiently: a naive approach is certainly not linear. –  András Salamon Jul 22 '10 at 12:53
I don't see what the trouble here is. This looks very linear to me. All you need is to maintain pointers between edges of G' and the corresponding nodes of T' so that you can perform each step in constant time. –  David Eppstein Jul 22 '10 at 17:37
I agree... having now thought about it more carefully this idea easily gives a linear algorithm. Run Valdes et. al. recognition algorithm to reduce the graph to a single edge, keeping track at each stage of which pair of edges were merged. Then build the tree by reversing these steps, with each stage involving creating one new internal node and one new leaf node, and adjusting pointers on three nodes, all of which is constant time. Of course it's obvious now I understand it, but is this why nobody bothers to write it down? –  Gordon Royle Jul 23 '10 at 0:11
I agree, for edge-series-parallel multigraphs this is linear. Apologies for the incorrect categorical statement that this approach isn't linear. –  András Salamon Jul 23 '10 at 10:20

I think David Speyer's answer is already good enough, but I thought I'd add as a separate answer that I have an old paper with an alternative method of recognizing series parallel graphs and their decomposition trees: Parallel recognition of series parallel graphs, D. Eppstein, Information & Computation 98:41-55, 1992.

The basic idea is to decompose the 2-connected components of the graph into a cycle and a sequence of paths, where the endpoints of each path belong to earlier pieces of the decomposition — this is called an "ear decomposition", is easy to find in linear time, and dates back to Whitney 1932. It turns out that a graph is 2-connected if and only if (in all possible ear decompositions) the two endpoints of each path belong to a single previous component and the intervals in each component formed by pairs of endpoints of paths are nested. The nesting structure lets one reconstruct the decomposition tree.

The paper is primarily about a model of parallel computing that very few people care about any more but it also provides conventional linear time algorithms.

-
Yes, I read your paper but couldn't quite figure out how to get the tree from the ear decomposition. Supposing we know the terminals in the final graph, is it possible to turn the following into a linear time algorithm (my analysis of algorithms skills are both limited and rusty). (1) If (G,s,t) has cut-vertices then it is a series-composition of a bunch of 2-connected pieces. Form node with these as children and recurse. (2) Otherwise if {s,t} is a 2-vertex cut then delete {s,t}, find the connected components G_1, .. G_k and note that G is parallel composition of the G_i+{s,t}, Recurse –  Gordon Royle Jul 23 '10 at 0:17
That sounds like it should work. Make sure to count an edge st (if it exists) as one of the components that you include in the parallel composition, though. –  David Eppstein Jul 23 '10 at 3:13

As you state, Valdes/Tarjan/Lawler is a recognition algorithm.

There has been a stream of work on actually finding modular decompositions. The recent work of Fabien de Montgolfier (with collaborators) is pretty definitive; they have also produced a C implementation. I did a Perl implementation of an older algorithm, and Nathann Cohen is currently working to incorporate de Montgolfier's code into the Sage framework (it looks like it should appear in version 4.5.2, due early August 2010).

-
Are we talking about the same thing here? I thought modular decompositions were related to cographs where "series composition" essentially means "disjoint union" and "parallel composition" essentially means "complete join". Here, I have two graphs with distinguished terminals (G,s,t) and (H,s',t') and the parallel composition identifies s with s' and t with t' but creates a new graph with these as the terminals. The series composition identifies t with s' and creates a new graph with s and t' as terminals (and t=s' as a cutvertex). –  Gordon Royle Jul 22 '10 at 13:37
Ah, you are asking about edge-series-parallel *multi*graphs. Valdes/Tarjan/Lawler start with vertex-series-parallel digraphs, turn these into edge-series-parallel multidigraphs by taking the line digraph, then work with these (they are trying to avoid the overhead of taking the transitive closure). The VTL approach is easier if you are starting with the multigraph. Modular decomposition is a general approach that applies to 2-structures, undirected graphs, posets, as well as directed graphs (anywhere where the idea of a module makes sense). –  András Salamon Jul 23 '10 at 10:12
This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$. This was proven by Bodlaender in this paper. Note that series-parallel graphs have tree-width at most 2. Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2 in linear-time. This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).