标题： 计算线性顶点arboricity的参数化复杂性 显示英文标题

标题： The Parameterized Complexity of Computing the Linear Vertex Arboricity

摘要： 一个图的线性顶点 Arboricity（记作 \emph{线性顶点 Arboricity}）是指可以将该图的顶点划分成的最少数量的集合，使得每个集合诱导出一个线性森林。 Chaplick 等人 [JoCG 2020] 表明，令人惊讶的是，一个图的线性顶点 Arboricity 与其线性跨度（记作 \emph{三维弱线覆盖数}）相同，即在一个无交叉的直线绘图中覆盖图的顶点所需的最小直线数（在 $\mathbb{R}^3$ 中）。 Chaplick 等人 [JGAA 2023] 表明，判断一个给定图是否具有线性顶点 Arboricity 为 2 是 NP 难问题。 本文研究了计算线性顶点 Arboricity 的参数复杂性。我们证明了该问题关于最大度参数是 para-NP 难的。 我们的结果在以下意义上是紧的：所有最大度为 4 的图（除了 $K_4$）的线性顶点 Arboricity 至多为 2，而我们表明，对于最大度为 5 的图，判断其线性顶点 Arboricity 是否为 2 是 NP 难的。 此外，我们表明，对于平面图，对于最大度为 6 的图，同样的问题是 NP 难的，而最大度为 5 的情况仍开放。 最后，我们证明，对于任意 $k \ge 1$，判断一个图的线性顶点 Arboricity 是否至多为 $k$ 是关于给定图的树宽固定参数可解的。 显示英文摘要

摘要： The \emph{linear vertex arboricity} of a graph is the smallest number of sets into which the vertices of a graph can be partitioned so that each of these sets induces a linear forest. Chaplick et al. [JoCG 2020] showed that, somewhat surprisingly, the linear vertex arboricity of a graph is the same as the \emph{3D weak line cover number} of the graph, that is, the minimum number of straight lines necessary to cover the vertices of a crossing-free straight-line drawing of the graph in $\mathbb{R}^3$. Chaplick et al. [JGAA 2023] showed that deciding whether a given graph has linear vertex arboricity 2 is NP-hard. In this paper, we investigate the parameterized complexity of computing the linear vertex arboricity. We show that the problem is para-NP-hard with respect to the parameter maximum degree. Our result is tight in the following sense. All graphs of maximum degree 4 (except for $K_4$) have linear vertex arboricity at most 2, whereas we show that it is NP-hard to decide, given a graph of maximum degree 5, whether its linear vertex arboricity is 2. Moreover, we show that, for planar graphs, the same question is NP-hard for graphs of maximum degree 6, leaving open the maximum-degree-5 case. Finally, we prove that, for any $k \ge 1$, deciding whether the linear vertex arboricity of a graph is at most $k$ is fixed-parameter tractable with respect to the treewidth of the given graph.