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

Abstract

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 $\ddot{I}{}^{\ast }$ and the source number $\hat{I}{\pm }_s$. On the one hand we give algorithms with running time $f(|\vec{H}|,d(\vec{G}))\cdot |\vec{G}{|}^{\ddot{I}{}^{\ast }(\vec{H})+O(1)}$ and $f(|\vec{H}|,d(\vec{G}))\cdot |\vec{G}{|}^{\hat{I}{\pm }_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 $\ddot{I}{}^{\ast }(\vec{C})$ ($\hat{I}{\pm }_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.

47 pages, 1 figure, abstract shortened due to arXiv requirements