论文标题
在有向图中计数模式计数的复杂性，由Outgree参数化
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
论文作者
论文摘要
我们研究以下基本问题的固定参数障碍性：给定两个定向图$ \ vec h $和$ \ vec g $，计算$ \ vec g $中$ \ vec h $的副本数量。易于理解的标准设置仅使用$ | \ vec h | $作为参数。在本文中，我们向前迈出了一步，并作为参数$ | \ vec h |+d（\ vec g）$采用，其中$ d（\ vec g）$是$ | \ vec g | $的最大超级。在此参数化下，我们通过两个新的结构参数，分数覆盖率$ρ^*$和源编号$α_s$在其非诱导和诱导版本中的固定参数障碍性。一方面，我们给出算法的运行时间$ f（| \ vec h |，d（\ vec g））\ cdot | \ vec g |^{ρ^*\！（\ vec h）+o（vec h）+o（1）} $ and $ f（| \ vec h |，d（\ vec g） h）+o（1）} $用于分别计数$ \ vec g $中的$ \ vec h $的副本和诱导副本;另一方面，我们表明，除非指数时间假设失败，否则对于任何类$ \ vec c $有向图的$ \ vec c $（诱导的）计数问题是固定参数时可固定的，并且仅当$ρ^*（\ vec c）$（$α_s（$α_s（\ vec c）$）时。这些结果解释了该模式的方向如何使计数变得容易或硬，并证明Chiba和Nishizeki及其扩展的经典算法（Chiba，Nishizeki Sicomp 85; Bressan Algorithmica 21）是最佳的。
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.
