2022/11/03 by Marco Bressan, Matthias Lanzinger, Bressan, Marco +3 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2211.01905
openalex publication_date 2022/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 (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.