Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees

Nagoya, Takayuki

doi:10.1515/fcds-2016-0010

Abstract

In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the prefix set of graph isomorphism. The former problem is known to be NP-complete, whereas the latter problem is known to be GI-complete. We propose polynomial time exact algorithms for these problems on partial k-trees.

References

[1] Arnborg S., Corneil D., and Proskurowski A., Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8, 1987, 277–284.10.1137/0608024
Search in Google Scholar Back to article
[2] Babel L., Ponomarenko I. N. and Tinhofer G., The Isomorphism Problems for directed Path Graphs and for Rooted Directed Path Graphs, J. Algorithms, 21, 1996, 542–564.10.1006/jagm.1996.0058
Search in Google Scholar Back to article
[3] Bodlaender H. L., Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 1990, 631–643.10.1016/0196-6774(90)90013-5
Search in Google Scholar Back to article
[4] Booth K. S. and Colbourn C. J., Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo, 1979
Search in Google Scholar Back to article
[5] Brandstädt A., Le V. B. and Spinrad J. P., Graph Classeses: A Survey, SIAM, 1999.10.1137/1.9780898719796
Search in Google Scholar Back to article
[6] Colbourn G.J., On testing isomorphism of permutation graphs, Networks, 11, 1981, 13–21.10.1002/net.3230110103
Search in Google Scholar Back to article
[7] Hopcroft J. and Karp R. M., An n5/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 4, 1975, 225–231.10.1137/0202019
Search in Google Scholar Back to article
[8] Köbler J. and Schöning U. and ToranJ., The Graph Isomorphism Problem: Its Structural Complexity, Birkhauser, 1993.10.1007/978-1-4612-0333-9
Search in Google Scholar Back to article
[9] Lee J., Han W. S., Kasperovics R., and Lee J. H., An indepth comparison of subgraph isomorphism algorithms in graph databases, Proceedings of the 39th international conference on Very Large Data Bases. VLDB Endowment, 2012, 133–144.10.14778/2535568.2448946
Search in Google Scholar Back to article
[10] Lubiw A., Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10(1), 1981, 11–21.10.1137/0210002
Search in Google Scholar Back to article
[11] Lueker G. S. and Booth K. S., A Linear Time Algorithm for deciding interval graph isomorphism, J. ACM, 26, 1979, 183–195.10.1145/322123.322125
Search in Google Scholar Back to article
[12] Matura D., Subtree isomorphism in O(n5/2), Annals of Discrete Mathematics, 2, 1978, 91–106.10.1016/S0167-5060(08)70324-8
Search in Google Scholar Back to article
[13] Nagoya T., Algorithms for Graph Isomorphism with Restriction on Chordal Graphs with Bounded Clique Size, IEICE Trans. Inf. & Sys., J95-D(11), 2012, 1889–1896.
Search in Google Scholar Back to article
[14] Nagoya T. and Toda S., Computational Complexity of Computing a Partial Solution for the Graph Automorphism Problems, Theor. Comput. Sci., 410, 2009, 2064–2071.10.1016/j.tcs.2009.01.001
Search in Google Scholar Back to article
[15] Saltz M., Jain A., Kothari A., Fard A., Miller J. A., Ramaswamy L., An Algorithm for Subgraph Pattern Matching on Very Large Labeled Graphs, IEEE International Congress on Big Data, 2014.10.1109/BigData.Congress.2014.79
Search in Google Scholar Back to article
[16] Toda S., Computing Automorphism Groups of Chordal Graphs Whose Simplicial Components Are of Small Size, IEICE Trans. Inf. & Sys., E89-D(8), 2006, 2388–2401.10.1093/ietisy/e89-d.8.2388
Search in Google Scholar Back to article
[17] Uehara R. and Uno Y., Laminar Structure of Ptolemaic Graphs with Applications. Disc. Appl. Math., 157, 2009, 1533–1543.10.1016/j.dam.2008.09.006
Search in Google Scholar Back to article

Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees

Abstract

Paradigm

My account