Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2015 | OriginalPaper | Chapter

On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling

Authors : Amihood Amir, Benny Porat

Published in: Combinatorial Pattern Matching

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measure is the minimum number of label swaps necessary to transform the graph from one labeling to the other, where a swap is the interchange of the labels of two adjacent nodes. We are interested in the complexity of determining the swap distance. The problem has been recently explored for various restricted classes of graphs, but its complexity in general graphs has not been established.
We show that the problem is \(\mathcal {NP}\)-hard. In addition we consider restricted versions of the problem where a node can only participate in a bounded number of swaps. We show that the problem is \(\mathcal {NP}\)-hard under these restrictions as well.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter A Framework for Space-Efficient String Kernels
Literature
1.
Agnarsson, G., Greenlaw, R., Kantabutra, S.: On the graph relabeling problem. Thai J. Math. 8(1), 21–42 (2010)MATHMathSciNet
2.
Akutsu, T.: A linear time pattern matching algorithm between a string and a tree. In: Proceedings of 4th Symposium on Combinatorial Pattern Matching (CPM), pp. 1–10, Padova (1993)
3.
Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \(\ell _{1}\) and \(\ell _{\infty }\) rearrangement distances. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 39–49. Springer, Heidelberg (2007) CrossRef
4.
5.
Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances. In: Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1221–1229 (2006)
6.
Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 118–129. Springer, Heidelberg (2008) CrossRef
7.
Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. In: Proceedings of 38th IEEE FOCS, pp. 144–153 (1997)
8.
Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. J. Algorithms 37(2), 247–266 (2000). (Preliminary version appeared at FOCS 1997)MATHMathSciNetCrossRef
9.
10.
11.
Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. SIAM J. Comp. 39(4), 1444–1461 (2009)MATHMathSciNetCrossRef
12.
Amir, A., Landau, G.M., Lewenstein, M., Lewenstein, N.: Efficient special cases of pattern matching with swaps. Inf. Process. Lett. 68(3), 125–132 (1998)MathSciNetCrossRef
13.
14.
15.
16.
Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: From coding theory to efficient pattern matching. In: Proceedings of 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 778–784 (2009)
17.
Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: k-Mismatch with don’t cares. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 151–162. Springer, Heidelberg (2007) CrossRef
18.
Clifford, R., Porat, E.: A Filtering algorithm for k-mismatch with don’t cares. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 130–136. Springer, Heidelberg (2007) CrossRef
19.
Cole, R., Hariharan, R.: Randomized swap matching in \(o(m \log m \log |\sigma |)\) time. Technical report TR1999-789, New York University, Courant Institute, September 1999
20.
Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: A faster implementation of the goemans-williamson clustering algorithm. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 17–25 (2001)
21.
Dombb, Y., Lipsky, O., Porat, B., Porat, E., Tsur, A.: Approximate swap and mismatch edit distance. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 149–163. Springer, Heidelberg (2007) CrossRef
22.
Duato, J.: A theory of fault-tolerant routing in wormhole networks. IEEE Trans. Parallel Distrib. Syst. 8(8), 790–802 (1997)CrossRef
23.
24.
Gallian, J.A.: A dynamic survey of graph labeling. Electronic Journal of Combinatorics 18, 1–219 (2011)
25.
26.
27.
Johnson, W.W., Woolsay, W.E.: Notes on the ‘15 puzzle’. Am. J. Math. 2(4), 397–404 (1879)MATHCrossRef
28.
Kantabutra, S.: The complexity of label relocation problems on graphs. In: Proceedings of 8th Asian Symposium of Computer Mathematics, National University of Singapore (2007)
29.
Kapah, O., Landau, G.M., Levy, A., Oz, N.: Interchange rearrangement: the element-cost model. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 224–235. Springer, Heidelberg (2008) CrossRef
30.
Kim, D.K., Park, K.: String matching in hypertext. In: Proceedings of 6th Symposium on Combinatorial Pattern Matching (CPM 1995) (1995)
31.
Lipsky, O., Porat, B., Porat, E., Shalom, B.R., Tzur, A.: Approximate string matching with swap and mismatch. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 869–880. Springer, Heidelberg (2007) CrossRef
32.
Manber, U., Wu, S.: Approximate string matching with arbitrary cost for text and hypertext. In: Proceedings International Workshop on Structural and Syntactic Pattern Recognition, pp. 22–33 (1992)
33.
Muir, T.: A treatise of the thoery of determinants with graduated sets of exercises. Macmillan and Co., London (1882)
34.
Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Zvi, Ukkonen, Esko (eds.) CPM 1995. LNCS, vol. 937, pp. 298–317. Springer, Heidelberg (1995) CrossRef
35.
Metadata
Title
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
Authors
Amihood Amir
Benny Porat
Copyright Year
2015
Book
Combinatorial Pattern Matching

Print ISBN: 978-3-319-19928-3

Electronic ISBN: 978-3-319-19929-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-19929-0_1

Premium Partner

    Image Credits