Top

Published in:

2017 | OriginalPaper | Chapter

Finding Cut-Vertices in the Square Roots of a Graph

Author : Guillaume Ducoffe

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

The square of a given graph \(H=(V,E)\) is obtained from H by adding an edge between every two vertices at distance two in H. Given a graph class \(\mathcal {H}\), the \(\mathcal {H}\)-Square Root problem asks for the recognition of the squares of graphs in \(\mathcal {H}\). In this paper, we answer positively to an open question of [Golovach et al. IWOCA 2016] by showing that the squares of cactus-block graphs can be recognized in polynomial time. Our proof is based on new relationships between the decomposition of a graph by cut-vertices and the decomposition of its square by clique cutsets. More precisely, we prove that the closed neighbourhoods of cut-vertices in H induce maximal subgraphs of \(G = H^2\) with no clique-cutset. Furthermore, based on this relationship, we can compute from a given graph G the block-cut tree of a desired square root (if any). Although the latter tree is not uniquely defined, we show surprisingly that it can only differ marginally between two different roots. Our approach not only gives the first polynomial-time algorithm for the \(\mathcal {H}\)-Square Root problem for several graph classes \(\mathcal {H}\), but it also provides a unifying framework for the recognition of the squares of trees, block graphs and cactus graphs—among others.

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

previous chapter Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes

next chapter The Minimum Shared Edges Problem on Grid-Like Graphs

Sufficient conditions for the framework to be applied are rather technical. They will be properly stated in a journal version.

The authors in [19] have rather focused on the stronger notion of important cut-vertices, that requires the existence of an additional third component \(C_3\) of \(G {\setminus } v\) such that \(C_3 \not \subseteq N_G(v)\). We do not use this notion in our paper.

Let \(\mathcal {H}\) be closed under edge deletion. If G has a square root in \(\mathcal {H}\) then there exists a finest square root \(H \in \mathcal {H}\) such that H is a minimal square root of G.

This first assumption on the blocks may look a bit artificial. However, we emphasize that it holds for every regular graph [3].

Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18(P139), 1 (2011)MathSciNetMATH

Agnarsson, G., Halldórsson, M.M.: Coloring powers of planar graphs. SIAM J. Discrete Math. 16(4), 651–662 (2003)CrossRefMathSciNetMATH

Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Appl. Math. 8(1), 1–12 (1984)CrossRefMathSciNetMATH

Berry, A., Pogorelcnik, R., Simonet, G.: Organizing the atoms of the clique separator decomposition into an atom tree. Discrete Appl. Math. 177, 1–13 (2014)CrossRefMathSciNetMATH

Bodlaender, H.-L., Kratsch, S., Kreuzen, V., Kwon, O.-J., Ok, S.: Characterizing width two for variants of treewidth. Discrete Appl. Math. 216(Part 1), 29–46 (2017)CrossRefMathSciNetMATH

Bonamy, M., Lévêque, B., Pinlou, A.: 2-distance coloring of sparse graphs. J. Graph Theory 77(3), 190–218 (2014)CrossRefMathSciNetMATH

Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics. Springer, London (2008)CrossRefMATH

Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212–232 (2001)CrossRefMathSciNetMATH

Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear-time algorithms for tree root problems. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 411–422. Springer, Heidelberg (2006). doi:10.1007/11785293_38 CrossRef

10.

Cochefert, M., Couturier, J.-F., Golovach, P.A., Kratsch, D., Paulusma, D.: Parameterized algorithms for finding square roots. Algorithmica 74(2), 602–629 (2016)CrossRefMathSciNetMATH

11.

Ducoffe, G.: Finding cut-vertices in the square roots of a graph. Technical report hal-01477981, UCA, Inria, CNRS, I3S, France (2017). https://hal.archives-ouvertes.fr/hal-01477981

12.

Ducoffe, G., Coudert, D.: Clique-decomposition revisited. In: Revision (Research Report on HAL, hal-01266147) (2017)

13.

Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. Technical report, arXiv arXiv:1210.7684 (2012)

14.

Farzad, B., Lau, L.C., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62(1–2), 38–53 (2012)CrossRefMathSciNetMATH

15.

Fleischner, H.: The square of every two-connected graph is Hamiltonian. J. Comb. Theory Ser. B 16(1), 29–34 (1974)CrossRefMathSciNetMATH

16.

Gallai, T.: Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutató Int. Közl 7, 3–36 (1962)MathSciNetMATH

17.

Golovach, P., Heggernes, P., Kratsch, D., Lima, P., Paulusma, D.: Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 275–288. Springer, Cham (2017). doi:10.1007/978-3-319-68705-6_z. arXiv:1703.05102

18.

Golovach, P., Kratsch, D., Paulusma, D., Stewart, A.: A linear kernel for finding square roots of almost planar graphs. In: SWAT, pp. 4:1–4:14 (2016)

19.

Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Finding cactus roots in polynomial time. In: Mäkinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 361–372. Springer, Cham (2016). doi:10.1007/978-3-319-44543-4_28 CrossRef

20.

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)MATH

21.

Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9(3), 314–320 (1988)CrossRefMathSciNetMATH

22.

Harary, F., Karp, R.M., Tutte, W.T.: A criterion for planarity of the square of a graph. J. Comb. Theory 2(4), 395–405 (1967)CrossRefMathSciNetMATH

23.

Heggernes, P.: Minimal triangulations of graphs: a survey. Discrete Math. 306(3), 297–317 (2006)CrossRefMathSciNetMATH

24.

Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)CrossRef

25.

Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms (TALG) 2(2), 178–208 (2006)CrossRefMathSciNetMATH

26.

Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Discrete Math. 18(1), 83–102 (2004)CrossRefMathSciNetMATH

27.

Le, V.B., Nguyen, N.T.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 111(3), 120–123 (2011)CrossRefMathSciNetMATH

28.

Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Math. 310(4), 734–741 (2010)CrossRefMathSciNetMATH

29.

Leimer, H.-G.: Optimal decomposition by clique separators. Discrete Math. 113(1–3), 99–123 (1993)CrossRefMathSciNetMATH

30.

Lih, K.-W., Wang, W.-F., Zhu, X.: Coloring the square of a \({K}_4\)-minor free graph. Discrete Math. 269(1), 303–309 (2003)CrossRefMathSciNetMATH

31.

Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L.: Powers of cycles, powers of paths, and distance graphs. Discrete Appl. Math. 159(7), 621–627 (2011)CrossRefMathSciNetMATH

32.

Lin, Y.-L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8(1), 99–118 (1995)CrossRefMathSciNetMATH

33.

Lloyd, E., Ramanathan, S.: On the complexity of distance-2 coloring. In: ICCI, pp. 71–74. IEEE (1992)

34.

Milanič, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161(10), 1538–1545 (2013)CrossRefMathSciNetMATH

35.

Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph. J. Comb. Theory Ser. B 94(2), 189–213 (2005)CrossRefMathSciNetMATH

36.

Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54(1), 81–88 (1994)CrossRefMathSciNetMATH

37.

Mukhopadhyay, A.: The square root of a graph. J. Comb. Theory 2(3), 290–295 (1967)CrossRefMathSciNetMATH

38.

Nestoridis, N.V., Thilikos, D.M.: Square roots of minor closed graph classes. Discrete Appl. Math. 168, 34–39 (2014)CrossRefMathSciNetMATH

39.

Le, V.B., Oversberg, A., Schaudt, O.: Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 360–371. Springer, Cham (2014). doi:10.1007/978-3-319-12340-0_30

40.

Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1–3), 171–188 (1997)CrossRefMathSciNetMATH

41.

Randerath, B., Volkmann, L.: A characterization of well covered block-cactus graphs. Australas. J. Comb. 9, 307–314 (1994)MathSciNetMATH

42.

Robertson, N., Seymour, P.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)CrossRefMathSciNetMATH

43.

Ross, I.C., Harary, F.: The square of a tree. Bell Syst. Tech. J. 39(3), 641–647 (1960)CrossRefMathSciNet

44.

Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221–232 (1985)CrossRefMathSciNetMATH

45.

Tucker, A.: Characterizing circular-arc graphs. Bull. Am. Math. Soc. 76(6), 1257–1260 (1970)CrossRefMathSciNetMATH

46.

Wegner, G.: Graphs with given diameter and a coloring problem. University of Dortmund, Technical report (1977)

Title: Finding Cut-Vertices in the Square Roots of a Graph
Author: Guillaume Ducoffe
Publisher: Springer International Publishing
Book: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-319-68704-9

Electronic ISBN: 978-3-319-68705-6

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-68705-6_18

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

Springer Professional "Wirtschaft"

Premium Partner