Grad and classes with bounded expansion II. Algorithmic aspects

Classes of graphs with bounded expansion have been introduced in [J. Nešetřil, P. Ossona de Mendez, The grad of a graph and classes with bounded expansion, in: A. Raspaud, O. Delmas (Eds.), 7th International Colloquium on Graph Theory, in: Electronic Notes in Discrete Mathematics, vol. 22, Elsevier (2005), pp. 101–106; J. Nešetřil, P. Ossona de Mendez, 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 CC and any integer pp there exists a constant N(C,p)N(C,p) so that the vertex set of any graph G∈CG∈C may be partitioned into at most N(C,p)N(C,p) parts, any i≤pi≤p parts of them induce a subgraph of tree-width at most (i−1)(i−1) [J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics (2005) (submitted for publication)] (actually, of tree-depth   [J. Nešetřil, P. Ossona de Mendez, Tree depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics 27 (6) (2006) 1022–1041] at most ii, which is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities [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)].We give here a simple algorithm for computing such partitions and prove that if we restrict the input graph to some fixed class CC with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed CC and pp).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 ϕϕ be a first-order logic sentence. We prove that any fixed graph property of type may be decided in linear time for input graphs in a fixed class with bounded expansion.We also show that for fixed pp, computing the distances between two vertices up to distance pp 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.