Abstract
The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe and Schweitzer [17] showing that the isomorphism problem for graphs of bounded clique-width is polynomial time.
B. Das—Part of the research was done while the author was a DIMACS postdoctoral fellow.
M.K. Enduri—Supported by Tata Consultancy Services (TCS) research fellowship.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In fact, it is an \({\textsf {AC}}^0\) reduction.
- 2.
In this case they are trivially structurally isomorphic via \(\pi \).
- 3.
Notice that this definition implies that \(G_{g_i}\) and \(H_{h_{\gamma (i)}}\) are isomorphic via the label map \(\pi _{i}\) where \(G_{g_i}\) and \(H_{h_{\gamma (i)}}\) are graphs generated by the parse trees \(T_{g_i}\) and \(T_{h_{\gamma (i)}}\) respectively.
- 4.
Bilabeling of a set \(X \subseteq V\) indicates that all the vertices in X are labeled with one label and \(V\setminus X\) is labeled with another label.
References
Babai, L.: Moderately exponential bound for graph isomorphism. In: Gécseg, F. (ed.) Fundamentals of Computation Theory. LNCS, vol. 117, pp. 34–50. Springer, Heidelberg (1981)
Babai, L.: Graph isomorphism in quasipolynomial time (2015). arXiv preprint arXiv:1512.03547
Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial \(k\)-trees. J. Algorithms 11(4), 631–643 (1990)
Bonamy, M.: A small report on graph and tree isomorphism (2010). http://bit.ly/1ySeNBn
Boppana, R.B., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127–132 (1987)
Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B., Rotics, U.: Polynomial-time recognition of clique-width 3 graphs. Discrete Appl. Math. 160(6), 834–865 (2012)
Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218–270 (1993)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125–150 (2000)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1), 77–114 (2000)
Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. CAAP’94. LNCS, vol. 787, pp. 68–84. Springer, Heidelberg (1994)
Cunningham, W.H.: A combinatorial decomposition theory. Can. J. Math. 32(3), 734–765 (1980)
Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods 3(2), 214–228 (1982)
Das, B., Enduri, M.K., Reddy, I.V.: Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 329–334. Springer, Heidelberg (2015)
Das, B., Enduri, M.K., Reddy, I.V.: Polynomial-time algorithm for isomorphism of graphs with clique-width at most 3. arXiv preprint (2015). arXiv:1506.01695
Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909–939 (2009)
Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Hungarica 18(1), 25–66 (1967)
Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1010–1029. IEEE (2015)
James, L.O., Stanton, R.G., Cowan, D.D.: Graph decomposition for undirected graphs. In: Proceedings of 3rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 281–290 (1972)
Kamiński, M., Lozin, V.V., Milanič, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747–2761 (2009)
Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In: IEEE 55th Annual Symposium on (FOCS), pp. 186–195 (2014)
Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42–65 (1982)
Ma, T.H., Spinrad, J.: An O(\(n^2\)) algorithm for undirected split decomposition. J. Algorithms 16(1), 145–160 (1994)
Miller, G.: Isomorphism testing for graphs of bounded genus. In: Proceedings of 12th Annual ACM Symposium on Theory of Computing, pp. 225–235. ACM (1980)
Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theor. Ser. B 96(4), 514–528 (2006)
Oum, S., Seymour, P.: Testing branch-width. J. Comb. Theor. Ser. B 97(3), 385–393 (2007)
Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 634–645. Springer, Heidelberg (2008)
Zemlyachenko, V., Konieko, N., Tyshkevich, R.: Graph isomorphism problem (Russian). In: The Theory of Computation I. Notes Sci. Sem. LOMI, vol. 118 (1982)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Das, B., Enduri, M.K., Reddy, I.V. (2016). Polynomial-Time Algorithm for Isomorphism of Graphs with Clique-Width at Most Three. In: Dinh, T., Thai, M. (eds) Computing and Combinatorics . COCOON 2016. Lecture Notes in Computer Science(), vol 9797. Springer, Cham. https://doi.org/10.1007/978-3-319-42634-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-42634-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42633-4
Online ISBN: 978-3-319-42634-1
eBook Packages: Computer ScienceComputer Science (R0)