论文标题
Digraph着色和距离无环的距离
Digraph Coloring and Distance to Acyclicity
论文作者
论文摘要
在$ k $ -Digraph的着色中，我们得到了一个挖掘物，并要求将其顶点分配到最多$ k $ sets中，以便每组都会引起DAG。这个众所周知的问题是np-hard，因为它概括（无向）$ k $颜色，但是如果输入挖掘物是无环的，则会变得微不足道。这提出了自然参数化的复杂性问题，当输入几乎是“无环”时会发生什么。在本文中，我们使用参数研究了这个问题，这些参数测量了指示或无向意义中输入的距离与无环的距离。 众所周知，对于所有$ k \ ge 2 $，$ k $ - digraph着色是DFV的digraphs of $ k+4 $的np-hard。我们加强了这一结果，以表明，对于所有$ k \ ge 2 $，$ k $ - digraph的着色是DFVS $ k $的NP-HARD。精炼我们的还原，我们获得了两个进一步的后果：（i）对于所有$ k \ ge 2 $，$ k $ - digraph的着色是反馈弧集（FAS）的NP-HARD，最多$ k^2 $;有趣的是，这导致了二分法，因为我们表明，如果FAS最多是$ k^2-1 $，则问题是$ k $； （ii）$ k $ -Digraph着色是DFVS $ K $的图表的NP-HARD，即使最高$δ$最多是$ 4K-1 $，也是$ K $的图形；我们证明这几乎也很紧，因为DFVS $ K $和$δ\ le 4K-3 $的问题变得fpt。 然后，我们考虑测量与基础图的无环的距离的参数。我们表明，$ k $ -Digraph着色承认了由TreeWidth参数化的FPT算法，其参数依赖性为$（TW！）K^{TW} $。然后，我们提出了一个问题，即是否可以消除$ tw！$ factor。我们在这一部分中的主要贡献是在负面问题中解决这个问题，并表明我们的算法基本上是最佳的，即使对于更受限制的参数TreeDeptth和$ k = 2 $也是如此。具体来说，我们表明，fpt算法求解了$ 2 $ -Digraph的颜色，并具有依赖性$ td^{o（td）} $与ETH相矛盾。
In $k$-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) $k$-Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. It is already known that, for all $k\ge 2$, $k$-Digraph Coloring is NP-hard on digraphs of DFVS at most $k+4$. We strengthen this result to show that, for all $k\ge 2$, $k$-Digraph Coloring is NP-hard for DFVS $k$. Refining our reduction we obtain two further consequences: (i) for all $k\ge 2$, $k$-Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most $k^2$; interestingly, this leads to a dichotomy, as we show that the problem is FPT by $k$ if FAS is at most $k^2-1$; (ii) $k$-Digraph Coloring is NP-hard for graphs of DFVS $k$, even if the maximum degree $Δ$ is at most $4k-1$; we show that this is also almost tight, as the problem becomes FPT for DFVS $k$ and $Δ\le 4k-3$. We then consider parameters that measure the distance from acyclicity of the underlying graph. We show that $k$-Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is $(tw!)k^{tw}$. Then, we pose the question of whether the $tw!$ factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for $k=2$. Specifically, we show that an FPT algorithm solving $2$-Digraph Coloring with dependence $td^{o(td)}$ would contradict the ETH.
