| Summary: | 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 adopt as a parameter |H→|+d(G→), where d(G→) is the maximum outdegree of |G→|. Under this parameterisation, 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 f(|H→|,d(G→)) · |G→|ρ*(H→)+O(1) and f(|H→|,d(G→)) · |G→|αs(H→)+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 restriction of the problem to patterns in C→ is fixed-parameter tractable if and only if ρ*(C→) is bounded (αs(C→) for the induced version). 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 and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.
Our proofs consist of several layers of parameterised 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 a careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertreewidth 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.
|
|---|