The Embedding Problem for Switching Classes of Graphs

• Autorzy: Ehrenfeucht A. , Hage J. , Harju T. , Rozenberg G.
• Języki publikacji: EN

Abstrakty

EN

In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a ``smaller'' graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group.

Słowa kluczowe

EN

seidel switching; graph algorithms; complexity; NP-completeness; embedding problem; cyclomatic number

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 1
• Strony: 115--134
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Ehrenfeucht A.

autor

Hage J.

autor

Harju T.

autor

Rozenberg G.

• Institute of Information and Computing Sciences, Utrecht University P.O. Box 80.089, 3508 TB, Utrecht the Netherlands,

Bibliografia

• [1] H. L. Bodlaender. A partial fc-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209:1-45, 1998.
• [2] D. G. Corneil and R. A. Mathon, editors. Geometry and Combinatorics: Selected Works of J. J. SeitJel. Academic Press. Boston, 1991.
• [3] R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer. 1998.
• [4] A. Ehrenfeucht, J. Hagę, T. Harju, and G. Rozenberg. Complexity issues in switching of graphs. In H. Ehrig, G. Engels. H.-J. Kreowski, and G. Rozenberg, editors, Theory And Application Of Graph Transformations -TAGT '98, volume 1764 of Lecture Notes in Computer Science, pages 59-70, Berlin, 2000. Springer Verlag.
• [5] A. Ehrenfeucht, J. Hagę, T. Harju, and G. Rozenberg. Embedding in switching ciasses with skew gains. In H. Ehrig, G. Engels, F. Parisi-Presicce, and G. Rozenberg, editors, Graph Transformations, SecondInternational Conference, ICGT 2004, volume LNCS 3256, pages 257 - 270. Springer Verlag. September/October 2004.
• [6] A. Ehrenfeucht, T. Harju, and G. Rozenberg. The Theory of2-Structures. World Scientific, Singapore, 1999.
• [7] A. Ehrenfeucht and G. Rozenberg. Dynamie labeled 2-structures. Mathematical Struclures in Computer Science, 4:433-455, 1994.
• [8] J. L. Gross and T. W. Tucker. Topological Graph Theory. Wiley, New York, 1987.
• [9] J. Hage.The membership problem for switching classes with skew gains. Fundamenta Informalicae, 39(4):375-387, 1999.
• [10] J. Hage.Structural Aspects Of Switching Classes. PhD thesis, Leiden Institute of Advanced Computer Science, 2001. http://www.cs.uu.nl/people/jur/2s.html.
• [11] F. Harary. Graph Theory. Addison Wesley. 1972.
• [12] J. J. Seidel. A survey of two-graphs. In Intern. Coli. Teorie Combinatorie (Roma,1973), volume I, pages 48l-5l1,Rome, 1976. Accad. Naz. Lincei. Reprinted in [2].
• [13] T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. /. Combin. Theory, Ser. B. 47:32-52. 1989.