The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth · arXiv (Cornell University) · 2022
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs $\vec H$ and $\vec G$, count the number of copies of $\vec H$ in $\vec G$. The standard setting, where the tractability is well understood, uses only $|\vec H|$ as a parameter. In this paper we take a step forward, and adopt as a parameter $|\vec H|+d(\vec G)$, where $d(\vec G)$ is the maximum outdegree of $|\vec 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 $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{ρ^*\!(\vec H)+O(1)}$ and $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{α_s(\vec H)+O(1)}$ for counting respectively the copies and induced copies of $\vec H$ in $\vec G$; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class $\vec C$ of directed graphs the (induced) counting problem is fixed-parameter tractable if and only if $ρ^*(\vec C)$ ($α_s(\vec 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.