The Parameterized Complexity of Computing the Linear Vertex Arboricity

The 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 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 R³. 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₄) 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 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.