Let S and T be the set of sources and sinks of a digraph G. Valdes et al. [16] defined the Series-Parallel digraph (SP- dags) as a digraph whose reduction transitive is a Minimal Series-Parallel-digraph (MSP-dags). An MSP digraph is any digraph that can be constructed starting with one vertex by applying two composition operators, a parallel composition which is the disjoint union of two MSP-dags, and a series composition which is the disjoint union of two MSP-dags G1 and G2 with adding the arcs of T1×S2. This famous class of digraphs has numerous theoretical and applied information technology applications. We show in this paper that if we consider the multiplication in the series operation as S1×T2, T1×T2, or S1×S2 then the obtained symmetric classes of series-parallel digraphs are recognizable in linear time.

[1] Aho A., Garey M., and Ullman J., “The Transitive Reduction of a Directed Graph,” SIAM Journal on Computing, vol. 1, no. 2, pp. 131-137, 1972. https://www.cs.tufts.edu/comp/150FP/archive/al- aho/transitive-reduction.pdf

[2] Baffi L. and Petreschi R., “Parallel Maximal Matching on Minimal Vertex Series-Parallel Digraphs,” in Proceedings of the Asian Computing Science Conference on Algorithms, Concurrency and Knowledge, Thailand, pp. 34-47, 1995. https://doi.org/10.1007/3-540-60688-2_33

[3] Bang-Jensen J. and Gutin G., Digraphs Theory, Algorithms and Applications, Springer, 2009. https://link.springer.com/book/10.1007/978-1- 84800-998-1

[4] Cormen T., Leiserson C., Rivest R., and Stein C., Introduction to Algorithms, The MIT Press, 2009. https://cdn.manesht.ir/19908___Introduction%20 to%20Algorithms.pdf

[5] Courcelle B., “The Monadic Second-Order Logic of Graphs VI: On Several Representations of Graphs by Relational Structures,” Discrete Applied Mathematics, vol. 54 no. 2-3, pp. 117- 149, 1994. https://doi.org/10.1016/0166- 218X(94)90019-1

[6] Courcelle B., Engelfriet J., and Rozenberg G., “Handle-Rewriting Hypergraph Grammars,” Journal of Computer and System Sciences, vol. 46, no. 2, pp. 218-270, 1993. https://doi.org/10.1016/0022-0000(93)90004-G

[7] Courcelle B., Handbook of Graph Grammars and Computing by Graph Transformation, 1997. https://doi.org/10.1142/9789812384720_0005

[8] Courcelle B., Makowsky J., and Rotics U., “Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width,” Theory of Computing Systems, vol. 33, pp. 125-150, 2000. https://doi.org/10.1007/s002249910009

[9] Culus J. and Demange M., “Oriented Coloring: Complexity and Approximation,” in Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Merin, pp. 226-236, 2006. https://link.springer.com/chapter/10.1007/116112 57_20

[10] Finta L., Liu Z., Mills I., and Bampis E., “Scheduling UET-UCT Series-parallel Graphs on Two Processors,” Theoretical Computer Science, vol. 162, no. 2, pp. 323-340, 1996. https://doi.org/10.1016/0304-3975(96)00035-7

[11] Fouquet J., Giakoumakis V., and Vanherpe J., “Bipartite Graphs Totally Decomposable by Canonical Decomposition,” International Journal of Foundations of Computer Science, vol. 10, no. 4, pp. 513-533, 1999. https://doi.org/10.1142/S0129054199000368

[12] Gurski F., Komander D., and Lindemann M., “Efficient Computation of the Oriented Chromatic Number of Recursively Defined Digraphs,” Theoretical Computer Science, vol. 890, pp. 16- 35, 2021. https://doi.org/10.1016/j.tcs.2021.08.013

[13] Kurt M., Berberler M., and Ugurlu O., “A New Algorithm for Finding Vertex-Disjoint Paths,” The International Arab Journal of Information 224 The International Arab Journal of Information Technology, Vol. 22, No. 2, March 2025 Technology, vol. 12, no. 6, pp. 550-555, 2015. https://iajit.org/PDF/vol.12,no.6/7418.pdf

[14] Oum S. and Seymour P., “Approximating Clique Width and Branch-Width,” Journal of Combinatorial Theory Series B, vol. 94, no. 4, pp. 514-528, 2006. https://doi.org/10.1016/j.jctb.2005.10.006

[15] Quaddoura R. and Al-Qerem A., “Bipartite (P6, C6)-Free Graphs: Recognition and Optimization Problems,” Symmetry, vol. 16, no. 4, pp. 1-14, 2024. https://doi.org/10.3390/sym16040447

[16] Valdes J., Tarjan R., and Lawler E., “The Recognition of Series-Parallel Digraphs,” SIAM Journal on Computing, vol. 11, no. 2, pp. 298-313, 1982. https://doi.org/10.1137/0211023