Motivated by the prevalence of multi-layer network structures in biological and social systems, we investigate the problem of counting the number of occurrences of (small) subgraphs or motifs in multi-layer graphs in which each layer of the graph has useful structural properties. Making use of existing meta-theorems, we focus on the parameterised complexity of motif-counting problems, giving conditions on the layers of a graph that yield fixed-parameter tractable algorithms for motif-counting in the overall graph. We give a dichotomy showing that, under some restricting assumptions, either the problem of counting the number of motifs is fixed-parameter tractable, or the corresponding decision problem is already W[1]-hard.
There is a rich literature concerning the (parameterised) complexity of finding and counting specific small pattern graphs in a large host graph. Several of the problems introduced in the seminal paper by Flum and Grohe on parameterised counting complexity @cite_29 are of this form, and very recently Curticapean, Dell and Marx @cite_17 gave a dichotomy for the parameterised complexity of counting so-called , based on the structure of the motifs under consideration.
@cite_29 @cite_17
2137874581 2610844084
We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W @math , for @math , that corresponds to Downey and Fellows's W-hierarchy [R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999] and we show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, is #W @math f(k) n^c @math f: N N @math 2^ O(k) n^ 2.376 $ algorithm for finding a cycle or path of length k [N. Alon, R. Yuster, and U. Zwick, J. ACM, 42 (1995), pp. 844--856]. We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovasz show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. We use the framework of graph motif parameters to obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G. More precisely, for graphs H on k edges, we show how to count subgraph copies of H in time kO(k)· n0.174k + o(k) by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k + c) time for k-edge matchings or O(n0.46k + c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f e C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class of graphs, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions.