6
$\begingroup$

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

Definition 1

  • start with K_2 marking both vertices as terminals
  • repeatedly join two smaller 2-terminal s/p graphs either in series or in parallel

Definition 2

  • start with K_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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Qiaochu Yuan
    Commented Jul 22, 2010 at 8:48

5 Answers 5

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Jul 22, 2010 at 12:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jul 22, 2010 at 17:37
  • $\begingroup$ 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? $\endgroup$
    – Gordon Royle
    Commented Jul 23, 2010 at 0:11
  • $\begingroup$ I agree, for edge-series-parallel multigraphs this is linear. Apologies for the incorrect categorical statement that this approach isn't linear. $\endgroup$
    – András Salamon
    Commented Jul 23, 2010 at 10:20
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Gordon Royle
    Commented Jul 23, 2010 at 0:17
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jul 23, 2010 at 3:13
2
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Gordon Royle
    Commented Jul 22, 2010 at 13:37
  • $\begingroup$ Ah, you are asking about edge-series-parallel multigraphs. 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). $\endgroup$
    – András Salamon
    Commented Jul 23, 2010 at 10:12
2
$\begingroup$

The answer can be found in Bodlaender, Fluiter 1996 "Parallel algorithms for series parallel graphs". They construct an sp-tree from an input graph if it is series-parallel.

[I know the question is three years old, but if that answer had been posted on this page, this would have saved me a lot of work. That's why I found it reasonable to answer it here, even now.]

Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Unfortunately the generic algorithm for bounded treewidth has a huge constant, depending on the tree automaton. I'm fairly convinced that a direct approach, such as the reference linear time algorithm for modular decomposition developed over the last decade, is going to beat such approaches for some time. $\endgroup$
    – András Salamon
    Commented Jul 22, 2010 at 13:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .