2025/05/24 by Alexander Erhardt, Erhardt, Alexander, Alexander Wolff +1
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2505.18885
openalex publication_date 2025/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℝ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 K4) 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.