Skip to main content

2017 | OriginalPaper | Buchkapitel

Finding Cut-Vertices in the Square Roots of a Graph

verfasst von : Guillaume Ducoffe

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
Sufficient conditions for the framework to be applied are rather technical. They will be properly stated in a journal version.
 
2
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.
 
3
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.
 
4
This first assumption on the blocks may look a bit artificial. However, we emphasize that it holds for every regular graph [3].
 
Literatur
1.
Zurück zum Zitat Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18(P139), 1 (2011)MathSciNetMATH Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Comb. 18(P139), 1 (2011)MathSciNetMATH
4.
Zurück zum Zitat 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 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
5.
Zurück zum Zitat 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 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
6.
7.
Zurück zum Zitat Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics. Springer, London (2008)CrossRefMATH Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics. Springer, London (2008)CrossRefMATH
8.
Zurück zum Zitat Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212–232 (2001)CrossRefMathSciNetMATH Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212–232 (2001)CrossRefMathSciNetMATH
9.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
12.
Zurück zum Zitat Ducoffe, G., Coudert, D.: Clique-decomposition revisited. In: Revision (Research Report on HAL, hal-01266147) (2017) Ducoffe, G., Coudert, D.: Clique-decomposition revisited. In: Revision (Research Report on HAL, hal-01266147) (2017)
13.
Zurück zum Zitat Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. Technical report, arXiv arXiv:1210.7684 (2012) Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. Technical report, arXiv arXiv:​1210.​7684 (2012)
14.
Zurück zum Zitat Farzad, B., Lau, L.C., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62(1–2), 38–53 (2012)CrossRefMathSciNetMATH 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.
16.
Zurück zum Zitat Gallai, T.: Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutató Int. Közl 7, 3–36 (1962)MathSciNetMATH Gallai, T.: Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutató Int. Közl 7, 3–36 (1962)MathSciNetMATH
17.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)MATH Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)MATH
22.
Zurück zum Zitat 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 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
24.
Zurück zum Zitat Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)CrossRef Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)CrossRef
26.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
30.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
33.
Zurück zum Zitat Lloyd, E., Ramanathan, S.: On the complexity of distance-2 coloring. In: ICCI, pp. 71–74. IEEE (1992) Lloyd, E., Ramanathan, S.: On the complexity of distance-2 coloring. In: ICCI, pp. 71–74. IEEE (1992)
34.
Zurück zum Zitat Milanič, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161(10), 1538–1545 (2013)CrossRefMathSciNetMATH Milanič, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Appl. Math. 161(10), 1538–1545 (2013)CrossRefMathSciNetMATH
35.
Zurück zum Zitat 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 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
38.
39.
Zurück zum Zitat 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 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.
Zurück zum Zitat Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1–3), 171–188 (1997)CrossRefMathSciNetMATH Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1–3), 171–188 (1997)CrossRefMathSciNetMATH
41.
Zurück zum Zitat Randerath, B., Volkmann, L.: A characterization of well covered block-cactus graphs. Australas. J. Comb. 9, 307–314 (1994)MathSciNetMATH Randerath, B., Volkmann, L.: A characterization of well covered block-cactus graphs. Australas. J. Comb. 9, 307–314 (1994)MathSciNetMATH
42.
46.
Zurück zum Zitat Wegner, G.: Graphs with given diameter and a coloring problem. University of Dortmund, Technical report (1977) Wegner, G.: Graphs with given diameter and a coloring problem. University of Dortmund, Technical report (1977)
Metadaten
Titel
Finding Cut-Vertices in the Square Roots of a Graph
verfasst von
Guillaume Ducoffe
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-68705-6_18