论文标题
有向图中的组件订单连接性
Component Order Connectivity in Directed Graphs
论文作者
论文摘要
如果每对$ x，y $的顶点为$ d，$在$ x $ y和$ y之间至少有一个弧线。是否有一个$ v $的子集$ x $ v $ size $ k $，以使$ d-x $中最大的强连接组件最多具有$ \ ell $ vertices。请注意，DCOC减少了$ \ ell = 1的有向反馈顶点集问题。特别是，我们证明，在半完整的挖掘中使用参数$ k $的DCOC可以在时间$ o^*（2^{16k}）$中求解，但不能在时间$ o^*（2^{o（k）}）$中求解，除非指数时间假设（enth）失败。 \ gutin {上限$ o^*（2^{16K}）$表示参数$ n- \ ell的上限$ o^*（2^{16（n- \ ell）}）$。我们改进\ vial {（（在$ \ ell $上依赖$ \ ell $）} g {Ö} ke，Marx and Mnich（2019）的上限，dcoc与$ o^*（k \ ell \ log（k \ ell）$ o^*^of参数$ \ ell+k $的时间复杂性与参数$ \ ell+k $ in $ o^*（k \ e \ ell）$（k o） （k \ ell））}）。 $ o^*（2^{o（k \ log k）}）。$
A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of $D,$ there is at least one arc between $x$ and $y.$ \viol{Thus, a tournament is a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC) problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and $\ell$, we are to decide whether there is a subset $X$ of $V$ of size $k$ such that the largest strong connectivity component in $D-X$ has at most $\ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $\ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, \ell,\ell+k$ and $n-\ell$. In particular, we prove that DCOC with parameter $k$ on semicomplete digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$ unless the Exponential Time Hypothesis (ETH) fails. \gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-\ell)})$ for the parameter $n-\ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-\ell})})$ unless ETH fails.} Finally, we improve \viol{(in dependency on $\ell$)} the upper bound of G{ö}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $\ell+k$ on general digraphs from $O^*(2^{O(k\ell\log (k\ell))})$ to $O^*(2^{O(k\log (k\ell))}).$ Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time $O^*(2^{o(k\log \ell)})$ unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity $O^*(2^{o(k\log k)}).$
