×

Grad and classes with bounded expansion. II: Algorithmic aspects. (English) Zbl 1185.05131

Summary: Classes of graphs with bounded expansion have been introduced in [(1) J. Nešetřil and P. Ossona de Mendez, The grad of a graph and classes with bounded expansion, in: A. Raspaud, The grad of a graph and classes with bounded expansion. A. Raspaud (ed.) et al., 7th international colloquium on graph theory, Hyeres, France, September 12–16, 2005. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 22, 101–106 (2005; Zbl 1182.05102), (2) Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics (2005) (submitted for publication)]. They generalize classes with forbidden topological minors (i.e. classes of graphs having no subgraph isomorphic to the subdivision of some graph in a forbidden family), and hence both proper minor closed classes and classes with bounded degree. For any class with bounded expansion \(\mathcal C\) and any integer \(p\) there exists a constant \(N({\mathcal C},p)\) so that the vertex set of any graph \(G\in{\mathcal C}\) may be partitioned into at most \(N({\mathcal C},p)\) parts, any \(i\leq p\) parts of them induce a subgraph of tree-width at most \((i-1)\) [(2)] (actually, of tree-depth [J. Nešetřil and P. Ossona de Mendez, Eur. J. Comb. 27, No. 6, 1022–1041 (2006; Zbl 1089.05025)] at most \(i\), which is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities [J. Nešetřil and P. Ossona de Mendez, Grad and classes with bounded expansion III. Restricted dualities, European Journal of Combinatorics (2005) (submitted for publication)]. We give here a simple algorithm for computing such partitions and prove that if we restrict the input graph to some fixed class \(\mathcal C\) with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed \(\mathcal C\) and \(p\)). This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion. More generally, let \(\phi\) be a first-order logic sentence. We prove that any fixed graph property of type
\[ \text{``}\exists X:(|X|\leq p)\wedge (G[X]\vDash\phi)\text{''} \]
may be decided in linear time for input graphs in a fixed class with bounded expansion. We also show that for fixed \(p\), computing the distances between two vertices up to distance \(p\) may be performed in constant time per query after a linear time preprocessing.
Also, extending several earlier results, we show that a class of graphs has sublinear separators if it has sub-exponential expansion. This result is best possible in general.

MSC:

05C83 Graph minors
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, P.D. Seymour, R. Thomas, A separator theorem for graphs with excluded minor and its applications, in: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 293-299; N. Alon, P.D. Seymour, R. Thomas, A separator theorem for graphs with excluded minor and its applications, in: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 293-299
[2] Alon, N.; Yuster, R.; Zwick, U., Color-coding, Journal of the Association for Computing Machinery, 42, 4, 844-856 (1995) · Zbl 0885.68116
[3] Chrobak, M.; Eppstein, D., Planar orientations with low out-degree and compaction of adjacency matrices, Theoretical Computer Science, 86, 243-266 (1991) · Zbl 0735.68015
[4] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9, 251-280 (1990) · Zbl 0702.65046
[5] Courcelle, B., Graph rewriting: An algebraic and logic approach, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. 2 (1990), Elsevier: Elsevier Amsterdam), 142-193, (Chapter 5) · Zbl 0900.68282
[6] Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information Computation, 85, 12-75 (1990) · Zbl 0722.03008
[7] Deogun, J. S.; Kloks, T.; Kratsch, D.; Muller, H., On vertex ranking for permutation and other graphs, (Enjalbert, P.; Mayr, E. W.; Wagner, K. W., Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 775 (1994), Springer), 747-758 · Zbl 0941.05516
[8] DeVos, M.; Ding, G.; Oporowski, B.; Sanders, D. P.; Reed, B.; Seymour, P. D.; Vertigan, D., Excluding any graph as a minor allows a low tree-width 2-coloring, Journal of Combinatorial Theory. Series B, 91, 25-41 (2004) · Zbl 1042.05036
[9] Eppstein, D., Subgraph isomorphism in planar graphs and related problems, (Proc. 6th Symp. Discrete Algorithms (January1995), ACM and SIAM), 632-640 · Zbl 0858.05075
[10] Eppstein, D., Subgraph isomorphism in planar graphs and related problems, Journal of Graph Algorithms & Applications, 3, 3, 1-27 (1999) · Zbl 0949.05055
[11] Eppstein, D., Diameter and treewidth in minor-closed graph families (Treewidth, graph minors, and algorithms), Algorithmica, 27, 275-291 (2000), (special issue) · Zbl 0963.05128
[12] Gilbert, J. R.; Hutchinson, J. P.; Tarjan, R. E., A separator theorem for graphs of bounded genus, Journal of Algorithms, 5, 375-390 (1984)
[13] Halin, R., \(S\)-functions for graphs, Journal of Geometry, 8, 171-176 (1976) · Zbl 0339.05108
[14] Kostochka, A. V.; Melnikov, L. S., On bounds of the bisection width of cubic graphs, (Nesetril, J.; Fiedler, M., Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (1992), Elsevier), 151-154 · Zbl 0773.05069
[15] Lipton, R.; Tarjan, R. E., A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, 36, 2, 177-189 (1979) · Zbl 0432.05022
[16] Miller, G. L.; Teng, S.-H.; Thurston, W.; Vavasis, S. A., Geometric separators for finite-element meshes, SIAM Journal on Scientific Computing, 19, 2, 364-386 (1998) · Zbl 0914.65123
[17] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics, 29, 3, 760-776 (2008) · Zbl 1156.05056
[18] J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion III. Restricted dualities, European Journal of Combinatorics (2005) (submitted for publication); J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion III. Restricted dualities, European Journal of Combinatorics (2005) (submitted for publication)
[19] Nešetřil, J.; Ossona de Mendez, P., The grad of a graph and classes with bounded expansion, (Raspaud, A.; Delmas, O., 7th International Colloquium on Graph Theory. 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics, vol. 22 (2005), Elsevier), 101-106 · Zbl 1182.05102
[20] Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (STOC’06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006), ACM Press), 391-400 · Zbl 1301.05268
[21] Nešetřil, J.; Ossona de Mendez, P., Tree depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, 27, 6, 1022-1041 (2006) · Zbl 1089.05025
[22] Nešetřil, J.; Poljak, S., Complexity of the subgraph problem, Commentationes Mathematicae Universitatis Carolinae, 26, 2, 415-420 (1985) · Zbl 0571.05050
[23] J. Nešetřil, I. Švejdarová, Diameter of duals are linear, Technical Report 2005-729, KAM-DIMATIA Series, Journal of Graph Theory (2005); J. Nešetřil, I. Švejdarová, Diameter of duals are linear, Technical Report 2005-729, KAM-DIMATIA Series, Journal of Graph Theory (2005) · Zbl 1139.05318
[24] P. Ossona de Mendez, Orientations bipolaires, Ph.D. Thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994; P. Ossona de Mendez, Orientations bipolaires, Ph.D. Thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994
[25] Plehn, J.; Voigt, B., Finding minimally weighted subgraphs, (Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science. Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 484 (1991), Springer-Verlag), 18-29 · Zbl 0768.68170
[26] Plotkin, S.; Rao, S.; Smith, W. D., Shallow excluded minors and improved graph decomposition, (5th Symp. Discrete Algorithms (1994), SIAM) · Zbl 0867.05069
[27] Robertson, N.; Seymour, P. D., Graph minors. I. Excluding a forest, Journal of Combinatorial Theory. Series B, 35, 39-61 (1983) · Zbl 0521.05062
[28] Robertson, N.; Seymour, P. D., Graph minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory. Series B, 89, 1, 43-76 (2003) · Zbl 1023.05040
[29] Schaffer, P., Optimal node ranking of trees in linear time, Information Processing Letters, 33, 91-96 (1989-90) · Zbl 0683.68038
[30] Teng, S.-H., Combinatorial aspects of geometric graphs, Computational Geometry, 9, 277-287 (1998) · Zbl 0894.68157
[31] R. Thomas, Problem Session of the Third Slovene Conference on Graph Theory, Bled, Slovenia, 1995; R. Thomas, Problem Session of the Third Slovene Conference on Graph Theory, Bled, Slovenia, 1995
[32] Wagner, K., Über eine Eigenschaft der Ebenen Komplexe, Mathematische Annalen, 114, 570-590 (1937) · JFM 63.0550.01
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.