Top

Theory of Computing Systems

Published in:

23-05-2016

The Behavior of Clique-Width under Graph Operations and Graph Transformations

Author: Frank Gurski

Published in: Theory of Computing Systems | Issue 2/2017

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

search-config

AI-assisted search

Off

Abstract

Clique-width is a well-known graph parameter. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded clique-width. The same holds for NLC-width. In this paper we study the behavior of clique-width and NLC-width under various graph operations and graph transformations. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs.

previous article Small-Bias is Not Enough to Hit Read-Once CNF

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 "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

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

Please note that by our definition the two graph transformations taking an induced subgraph of a graph and adding an edge to a graph are no graph operations.

Thus we do not consider graphs with loops or multiple edges.

The operations in the definition of clique-width were first considered by Courcelle, Engelfriet, and Rozenberg in [20].

The abbreviation NLC results from the node label controlled embedding mechanism originally defined for graph grammars.

To distinguish between the vertices of (non-tree) graphs and trees, we simply call the vertices of trees nodes.

The concept of tree-width already appeared in a work of Halin [37].

We implemented an algorithm which takes as input a graph G and an integer k and which decides whether nlcw(G) ≤ k.

The application of three local complementations at v, at v ₀, and again at v for some edge {v, v ₀} is also known as pivoting the edge {v, v ₀}, see [55].

Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey. BIT 25, 2–23 (1985)MathSciNetCrossRefMATH

Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discret. Appl. Math. 23, 11–24 (1989)MathSciNetCrossRefMATH

Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)MathSciNetCrossRefMATH

Boliac, R., Lozin, V.V.: On a the clique-width of graphs in hereditary classes. In: Proceedings of the international symposium on algorithms and computation, volume 2518 of LNCS. Springer-Verlag, pp. 44–54 (2002)

Bondy, J., Murty, U.: Graph Theory with Applications. North-Holland (1976)

Bouchet, A.: Circle graph obstructions. J. Comb. Theory. Series B 60, 107–144 (1994)MathSciNetCrossRefMATH

Bouvier, T.: Graphes et décompositions. Doctoral dissertation, Bordeaux University (2014)

Brandstädt, A., Dragan, F.F., Le, H.-O., Mosca, R.: New graph classes of bounded clique width. Theory Comput. Syst. 38(5), 623–645 (2005)MathSciNetCrossRefMATH

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)CrossRef

10.

Chvatalova, J., Opatrny, J.: The bandwidth problem and operations on graphs. Discret. Math. 61(2–3), 141–150 (1986)MathSciNetCrossRefMATH

11.

Colbourn, C.J., Corneil, D.G.: On deciding switching equivalence of graphs. Discret. Appl. Math. 2, 181–184 (1980)MathSciNetCrossRefMATH

12.

Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B., Rotics, U.: Polynomial time recognition of clique-width at most three graphs. Discret. Appl. Math. 160, 834–865 (2012)CrossRefMATH

13.

Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926–934 (1985)MathSciNetCrossRefMATH

14.

Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 4, 825–847 (2005)MathSciNetCrossRefMATH

15.

Courcelle, B.: The Monadic Second-Order Logic of Graphs XV: A conjecture by D. Seese. J. Appl. Logic 4, 79–114 (2006)MathSciNetCrossRefMATH

16.

Courcelle, B.: Clique-width and edge contraction. Inf. Process. Lett. 114, 42–44 (2014)MathSciNetCrossRefMATH

17.

Courcelle, B.: Fly-automata for checking monadic second-order properties of graphs of bounded tree-width. Electron. Notes Discret. Math. 50, 3–8 (2015). Proceedings of the VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS’15)CrossRefMATH

18.

Courcelle, B., Durand, I.: Automata for the verification of monadic second-order graph properties. J. Appl. Logic 10(4), 368–409 (2012)MathSciNetCrossRefMATH

19.

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2012)MATH

20.

Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218–270 (1993)MathSciNetCrossRefMATH

21.

Courcelle, B., Heggernes, P., Meister, D., Papadopoulos, C., Rotics, U.: A characterisation of clique-width through nested partitions. Discret. Appl. Math. 187, 70–81 (2015)MathSciNetCrossRefMATH

22.

Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)MathSciNetCrossRefMATH

23.

Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101, 77–114 (2000)MathSciNetCrossRefMATH

24.

Courcelle, B., Twigg, A.: Constrained-path labellings on graphs of bounded clique-width. Theory Comput. Syst. 47(2), 531–567 (2010)MathSciNetCrossRefMATH

25.

de Montgolfier, F., Rao, M.: The bi-join decomposition. Electron. Notes Discret. Math. 22, 173–177 (2005)CrossRefMATH

26.

Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Proceedings of Graph-Theoretical Concepts in Computer Science, volume 2204 of LNCS. Springer-Verlag, pp. 117–128 (2001)

27.

Espelage, W., Gurski, F., Wanke, E.: Deciding clique-width for graphs of bounded tree-width. J. Graph Algor. Appl. Special Issue JGAA on WADS 2001 7(2), 141–180 (2003)MathSciNetMATH

28.

Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discret. Math. 23(2), 909–939 (2009)MathSciNetCrossRefMATH

29.

Frucht, R., Haray, F.: On the coronas of two graphs. Aequationes Math. 4, 322–324 (1970)MathSciNetCrossRef

30.

Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000)MathSciNetCrossRefMATH

31.

Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without K _{n, n}. In: Proceedings of Graph-Theoretical Concepts in Computer Science, volume 1938 of LNCS. Springer-Verlag, pp. 196–205 (2000)

32.

Gurski, F., Wanke, E.: On the relationship between NLC-width and linear NLC-width. Theor. Comput. Sci. 347(1–2), 76–89 (2005)MathSciNetCrossRefMATH

33.

Gurski, F., Wanke, E.: Vertex disjoint paths on clique-width bounded graphs. Theor. Comput. Sci. 359(1–3), 188–199 (2006)MathSciNetCrossRefMATH

34.

Gurski, F., Wanke, E.: Line graphs of bounded clique-width. Discret. Math. 307(22), 2734–2754 (2007)MathSciNetCrossRefMATH

35.

Gurski, F., Wanke, E., Yilmaz, E.: Directed NLC-width. Theor. Comput. Sci. 616, 1–17 (2016)MathSciNetCrossRefMATH

36.

Hagerup, T.: Dynamic algorithms for graphs of bounded treewidth. Algorithmica 27(3), 292–315 (2000)MathSciNetCrossRefMATH

37.

Halin, R.: S-functions for graphs. J. Geom. 8, 171–176 (1976)CrossRefMATH

38.

Harary, F.: Graph Theory. Addison-Wesley Publishing Company, Massachusetts (1969)MATH

39.

Hayward, R.B.: Recognizing P ₃-structure: A switching approach. J. Comb. Theory Series B 66(2), 247–262 (1996)CrossRefMATH

40.

Heule, M.J.H., Szeider, S.: A sat approach to clique-width. ACM Trans. Comput. Logic 16(3), 24,1–24,27 (2015)MathSciNetCrossRefMATH

41.

Hlinený, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2008)CrossRef

42.

Imrich, W., Klavzar, S.: Product Graphs: Structure and Recognition. Series in Discrete Mathematics and Optimization. Wiley-Interscience (2000)

43.

Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, New York (1994)CrossRefMATH

44.

Johansson, Ö.: Clique-decomposition, NLC-decomposition, and modular decomposition - relationships and results for random graphs. Congressus Numerantium 132, 39–60 (1998)MathSciNetMATH

45.

Johansson, Ö.: NLC₂-decomposition in polynomial time. Int. J. Found. Comput. Sci. 11(3), 373–395 (2000)CrossRefMATH

46.

Kaminski, M., Lozin, V.V., Milanic, M.: Recent developments on graphs of bounded clique-width. Discret. Appl. Math. 157, 2747–2761 (2009)MathSciNetCrossRefMATH

47.

Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discret Appl. Math. 126(2–3), 197–221 (2003)MathSciNetCrossRefMATH

48.

Kashem, M.A., Zhou, X., Nishizeki, T.: Algorithms for generalized vertex-rankings of partial k-trees. Theor. Comput. Sci. 240(2), 407–427 (2000)MathSciNetCrossRefMATH

49.

Lackner, M., Pichler, R., Rümmele, S., Woltran, S.: Multicut on graphs of bounded clique-width. In: Proceedings of the International Conference on Combinatorial Optimization and Applications, volume 7402 of LNCS. Springer-Verlag, pp. 115–126 (2012)

50.

Limouzy, V.: Seidel minor, permutation graphs and combinatorial properties. In: Proceedings of the International Symposium on Algorithms and Computation, volume 6506 of LNCS. Springer-Verlag, pp. 194–205 (2010)

51.

Limouzy, V., de Montgolfier, F., Rao, M.: NLC-2 graph recognition and isomorphism. In: Proceedings of Graph-Theoretical Concepts in Computer Science, volume 4769 of LNCS. Springer-Verlag, pp. 86–98 (2007)

52.

Lozin, V., Rautenbach, D.: Chordal bipartite graphs of bounded tree- and clique-width. Discret. Math. 283, 151–158 (2004)MathSciNetCrossRefMATH

53.

Lozin, V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex dregree. SIAM J. Discret. Math. 18(1), 195–206 (2004)CrossRefMATH

54.

Oum, S.: Graphs of Bounded Rank-width. PhD thesis. Princeton University, New Jersey (2005)

55.

Oum, S.: Rank-width and vertex-minor. J. Comb. Theory Series B 95, 79–100 (2005)MathSciNetCrossRefMATH

56.

Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory Series B 96(4), 514–528 (2006)MathSciNetCrossRefMATH

57.

Robertson, N., Seymour P.D: Graph Minors – A Survey. Cambridge University Press, pp. 153–171 (1985)

58.

Robertson, N., Seymour, P.D.: Graph minors II: Algorithmic aspects of tree width. J. Algorithms 7, 309–322 (1986)MathSciNetCrossRefMATH

59.

Seidel, J.J.: Graphs and two-graphs. In: Proceedings of the 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Utilitas Mathematica Publishing (1974)

60.

Seidel, J.J.: A survey of two-graphs. In: Proceedings of Colloquio Internazionale sulle Teorie Combinatorie, vol. 17, pp. 481–511. Accademia Nazionale dei Lincei (1976)

61.

Seidel, J.J., Taylor, D.E.: Two-graphs, a second survey. In: Algebraic Methods in Graph Theory, vol. II, pp. 689–711 (1981)

62.

Suchan, K., Todinca, I.: On powers of graphs of bounded NLC-width (clique-width). Discret. Appl. Math. 155(14), 1885–1893 (2007)MathSciNetCrossRefMATH

63.

Wanke, E. Discret. Appl. Math. 54, 251–266 (1994)MathSciNetCrossRef

64.

Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math. 54, 150–168 (1932)MathSciNetCrossRefMATH

Title: The Behavior of Clique-Width under Graph Operations and Graph Transformations
Author: Frank Gurski
Publication date: 23-05-2016
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-016-9685-1

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2017

Composition Closure of Linear Extended Top-down Tree Transducers

A Difference in Complexity Between Recursion and Tail Recursion

Sophistication vs Logical Depth

Fixed Points, Nash Equilibria, and the Existential Theory of the Reals

Small-Bias is Not Enough to Hit Read-Once CNF

Distance Vector-based Advance Reservation with Delay Performance Guarantees

Premium Partner