Abstract
For similarity measures of labeled and unlabeled graphs, we study the complexity of the graph isomorphism problem for pairs of input graphs which are close with respect to the measure. More precisely, we show that for every fixed integer k we can decide in quadratic time whether a labeled graph G can be obtained from another labeled graph H by relabeling at most k vertices. We extend the algorithm solving this problem to an algorithm determining the number ℓ of vertices that must be deleted and the number k of vertices that must be relabeled in order to make the graphs equivalent. The algorithm is fixed-parameter tractable in k + ℓ.
Contrasting these tractability results, we also show that for those similarity measures that change only by finite amount d whenever one edge is relocated, the problem of deciding isomorphism of input pairs of bounded distance d is equivalent to solving graph isomorphism in general.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Borgs, C., Chayes, J.T., Lovász, L., Sós, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing. In: STOC 2006, New York, pp. 261–270 (2006)
Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters 18(8), 689–694 (1997)
Bunke, H.: Error correcting graph matching: on the influence of the underlying cost function. Pattern Analysis and Machine Intelligence 21(9), 917–922 (1999)
Chartrand, G., Saba, F., Zou, H.-B.: Edge rotations and distance between graphs. Časopis Pěst. Mat. 110(1), 87–91 (1985)
Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 238–249. Springer, Heidelberg (2006)
Cvetković, D.M., Rowlinson, P., Simić, S.: Eigenspaces of Graphs. Cambridge University Press, Cambridge (1997)
Dénes, J.: The representation of a permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 4, 63–71 (1959)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, London (1998)
Evdokimov, S., Ponomarenko, I.N.: Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks. Combinatorica 19(3), 321–333 (1999)
Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: STOC 1980, pp. 236–243 (1980)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, London (2006)
Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: FOCS 1980, Washington, USA, pp. 36–41 (1980)
Johnson, M.: An ordering of some metrics defined on the space of graphs. Czechoslovak Math. J. 37(112), 75–85 (1987)
Köbler, J., Schöning, U., Torán, J.: The graph isomorphism problem: its structural complexity. Birkhäuser Verlag, Basel (1993)
Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 81–92. Springer, Heidelberg (2010)
Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences 25(1), 42–65 (1982)
Marcu, D.: Note on the edge rotation distance between trees. International Journal of Computer Mathematics 30(1), 13–15 (1989)
Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: STOC 1980, New York, pp. 225–235 (1980)
Schweitzer, P.: Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Phd thesis, Universität des Saarlandes, Saarbrücken (2009)
Wilson, R.C., Zhu, P.: A study of graph spectra for comparing graphs and trees. Pattern Recognition 41(9), 2833–2841 (2008)
Yamazaki, K., Bodlaender, H.L., de Fluiter, B., Thilikos, D.M.: Isomorphism for graphs of bounded distance width. Algorithmica 24(2), 105–127 (1999)
Zelinka, B.: On a certain distance between isomorphism classes of graphs. Časopis Pěst. Mat. 100(4), 371–373 (1975)
Zelinka, B.: Contraction distance between isomorphism classes of graphs. Časopis Pěst. Mat. 115(2), 211–216 (1990)
Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. Journal of Mathematical Sciences 29(4), 1426–1481 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schweitzer, P. (2011). Isomorphism of (mis)Labeled Graphs. In: Demetrescu, C., Halldórsson, M.M. (eds) Algorithms – ESA 2011. ESA 2011. Lecture Notes in Computer Science, vol 6942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23719-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-23719-5_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23718-8
Online ISBN: 978-3-642-23719-5
eBook Packages: Computer ScienceComputer Science (R0)