The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree

We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H and G, count the number of copies of H in G. The standard setting, where the tractability is well understood, uses only | H| as a parameter. In this paper we take a step forward, and adopt as a parameter | H|+d( G), where d( G) is the maximum outdegree of | G|. Under this parameterization, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ * and the source number α s . On the one hand we give algorithms with running time +O(1) for counting respectively the copies and induced copies of H in G; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C of directed graphs the (induced) counting problem is fixed-parameter tractable if and only if ρ * ( C) (α s ( C)) is bounded. These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba, Nishizeki SICOMP 85; Bressan Algorithmica 21) are optimal unless ETH fails. Our proofs consist of several layers of parameterized reductions that preserve the outdegree of the host graph. To start with, we establish a tight connection between counting homomorphisms from H to G to #CSP, the problem of counting solutions of constraint satisfactions problems, for special classes of patterns that we call canonical DAGs. To lift these results from canonical DAGs to arbitrary directed graphs, we exploit a combination of several ingredients: existing results for #CSPs (Marx JACM 13; Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean, Dell, Marx STOC 17) to our setting, the introduction of what we call monotone reversible minors, and careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertree width as a function to our novel parameters. Along the route we establish a novel bound of the integrality gap for the fractional independence number of hypergraphs based on adaptive width, which might be of independent interest.