×

zbMATH — the first resource for mathematics

Finding cut-vertices in the square roots of a graph. (English) Zbl 1406.05101
Summary: 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 P. A. Golovach et al. [Lect. Notes Comput. Sci. 9843, 361–372 (2016; Zbl 1391.68051)] 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.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
05C76 Graph operations (line graphs, products, etc.)
Software:
Algorithm 447
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adamaszek, A.; Adamaszek, M., Uniqueness of graph square roots of girth six, Electron. J. Combin., 18, P139, 1, (2011) · Zbl 1222.05038
[2] Agnarsson, G.; Halldórsson, M. M., Coloring powers of planar graphs, SIAM J. Discrete Math., 16, 4, 651-662, (2003) · Zbl 1029.05047
[3] Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1, 1-12, (1984) · Zbl 0539.05052
[4] Berry, A.; Bordat, J.-P., Moplex elimination orderings, Electron. Notes Discrete Math., 8, 6-9, (2001) · Zbl 1409.05194
[5] 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) · Zbl 1297.05051
[6] A. Berry, G. Simonet, Computing the atom graph of a graph and the union join graph of a hypergraph. Technical Report arXiv:1607.02911, arXiv, 2016.
[7] Bodlaender, H. L., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1, 1-45, (1998) · Zbl 0912.68148
[8] 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) · Zbl 1350.05116
[9] Bonamy, M.; Lévêque, B.; Pinlou, A., 2-distance coloring of sparse graphs, J. Graph Theory, 77, 3, 190-218, (2014) · Zbl 1304.05042
[10] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Grad. Texts in Math., (2008))
[11] Bouchitté, V.; Todinca, I., Treewidth and minimum fill-in: Grouping the minimal separators, SIAM J. Comput., 31, 1, 212-232, (2001) · Zbl 0987.05085
[12] Chang, M.-S.; Ko, M.-T.; Lu, H.-I., Linear-time algorithms for tree root problems, (SWAT, (2006), Springer), 411-422 · Zbl 1142.05365
[13] Chaplick, S.; Töpfer, M.; Voborník, J.; Zeman, P., On \(H\)-topological intersection graphs, (International Workshop on Graph-Theoretic Concepts in Computer Science, (2017), Springer), 167-179 · Zbl 06821997
[14] Cochefert, M.; Couturier, J.-F.; Golovach, P. A.; Kratsch, D.; Paulusma, D., Parameterized algorithms for finding square roots, Algorithmica, 74, 2, 602-629, (2016) · Zbl 1332.05136
[15] Coudert, D.; Ducoffe, G., Revisiting decomposition by clique separators, SIAM J. Discrete Math., 32, 1, 682-694, (2018) · Zbl 1383.05256
[16] Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75, (1990) · Zbl 0722.03008
[17] Duchet, P.; Las Vergnas, M.; Meyniel, H., Connected cutsets of a graph and triangle bases of the cycle space, Discrete Math., 62, 2, 145-154, (1986) · Zbl 0609.05032
[18] Ducoffe, G., Finding cut-vertices in the square roots of a graph, (International Workshop on Graph-Theoretic Concepts in Computer Science, (2017), Springer), 234-248 · Zbl 06822002
[19] B. Farzad, M. Karimi, Square-root finding problem in graphs, a complete dichotomy theorem, Technical Report arXiv:1210.7684, arXiv, 2012.
[20] Farzad, B.; Lau, L. C.; Tuy, N. N., Complexity of finding graph roots with girth conditions, Algorithmica, 62, 1-2, 38-53, (2012) · Zbl 1239.05127
[21] Fleischner, H., The square of every two-connected graph is hamiltonian, J. Combin. Theory Ser. B, 16, 1, 29-34, (1974) · Zbl 0256.05121
[22] Gallai, T., Graphen mit triangulierbaren ungeraden Vielecken, Magyar Tud. Akad. Mat. Kutató Int. Közl, 7, 3-36, (1962) · Zbl 0132.21101
[23] Golovach, P.; Kratsch, D.; Paulusma, D.; Stewart, A., A linear kernel for finding square roots of almost planar graphs, Theoret. Comput. Sci., 689, 36-47, (2017) · Zbl 1372.05052
[24] Golovach, P.; Kratsch, D.; Paulusma, D.; Stewart, A., Finding cactus roots in polynomial time, Theory Comput. Syst., 62, 6, 1409-1426, (2018) · Zbl 1391.68052
[25] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Vol. 57, (2004), Elsevier
[26] Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 3, 314-320, (1988) · Zbl 0651.68083
[27] Harary, F.; Karp, R. M.; Tutte, W. T., A criterion for planarity of the square of a graph, J. Combin. Theory, 2, 4, 395-405, (1967) · Zbl 0153.25902
[28] Heggernes, P., Minimal triangulations of graphs: A survey, Discrete Math., 306, 3, 297-317, (2006) · Zbl 1086.05069
[29] Hopcroft, J.; Tarjan, R., Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM, 16, 6, 372-378, (1973)
[30] Lau, L. C., Bipartite roots of graphs, ACM Trans. Algorithms (TALG), 2, 2, 178-208, (2006) · Zbl 1321.05209
[31] Lau, L. C.; Corneil, D. G., Recognizing powers of proper interval, split, and chordal graphs, SIAM J. Discrete Math., 18, 1, 83-102, (2004) · Zbl 1071.05031
[32] Le, V. B.; Nguyen, N. T., A good characterization of squares of strongly chordal split graphs, Inform. Process. Lett., 111, 3, 120-123, (2011) · Zbl 1259.05168
[33] Le, V. B.; Tuy, N. N., The square of a block graph, Discrete Math., 310, 4, 734-741, (2010) · Zbl 1214.05145
[34] Leimer, H.-G., Optimal decomposition by clique separators, Discrete Math., 113, 1-3, 99-123, (1993) · Zbl 0793.05128
[35] 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) · Zbl 1027.05042
[36] 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) · Zbl 1213.05148
[37] Lin, Y.-L.; Skiena, S. S., Algorithms for square roots of graphs, SIAM J. Discrete Math., 8, 1, 99-118, (1995) · Zbl 0821.05052
[38] Lloyd, E.; Ramanathan, S., On the complexity of distance-2 coloring, (ICCI, (1992), IEEE), 71-74
[39] McConnell, R. M., Linear-time recognition of circular-arc graphs, (FOCS’01, (2001), IEEE), 386-394
[40] Milanič, M.; Schaudt, O., Computing square roots of trivially perfect and threshold graphs, Discrete Appl. Math., 161, 10, 1538-1545, (2013) · Zbl 1287.05095
[41] Molloy, M.; Salavatipour, M. R., A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B, 94, 2, 189-213, (2005) · Zbl 1071.05036
[42] Motwani, R.; Sudan, M., Computing roots of graphs is hard, Discrete Appl. Math., 54, 1, 81-88, (1994) · Zbl 0812.68103
[43] Mukhopadhyay, A., The square root of a graph, J. Combin. Theory, 2, 3, 290-295, (1967) · Zbl 0153.26001
[44] Nestoridis, N. V.; Thilikos, D. M., Square roots of minor closed graph classes, Discrete Appl. Math., 168, 34-39, (2014) · Zbl 1285.05165
[45] Oversberg, A.; Schaudt, O., Polynomial time recognition of squares of ptolemaic graphs and 3-sun-free split graphs, (WG, (2014), Springer), 360-371 · Zbl 1417.05221
[46] Parra, A.; Scheffler, P., Characterizations and algorithmic applications of chordal graph embeddings, Discrete Appl. Math., 79, 1-3, 171-188, (1997) · Zbl 0887.05044
[47] Randerath, B.; Volkmann, L., A characterization of well covered block-cactus graphs, Australas. J. Combin, 9, 307-314, (1994) · Zbl 0805.05070
[48] Robertson, N.; Seymour, P., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322, (1986) · Zbl 0611.05017
[49] Ross, I. C.; Harary, F., The square of a tree, Bell Syst. Tech. J., 39, 3, 641-647, (1960)
[50] Shibata, Y., On the tree representation of chordal graphs, J. Graph Theory, 12, 3, 421-428, (1988) · Zbl 0654.05022
[51] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 2, 221-232, (1985) · Zbl 0572.05039
[52] Tucker, A., Characterizing circular-arc graphs, Bull. Amer. Math. Soc., 76, 6, 1257-1260, (1970) · Zbl 0204.24401
[53] G. Wegner, Graphs with given diameter and a coloring problem. Technical report, Univ. Dortmund, 1977.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.