2023/04/06 by Agnijo Banerjee, João Pedro Marciano, Banerjee, Agnijo +7
Computer Science · #05C70 #68Q15 #68Q17 #68R05 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2304.03256
openalex publication_date 2023/04/06 · openalex created_date 2023/04/09 · openalex updated_date 2026/07/28
Deciding whether a graph can be edge-decomposed into a matching and a k-bounded linear forest was recently shown by Campbell, Hörsch and Moore to be NP-complete for every k ≥ 9, and solvable in polynomial time for k=1,2. In the first part of this paper, we close this gap by showing that this problem is in NP-complete for every k ≥ 3. In the second part of the paper, we show that deciding whether a graph can be edge-decomposed into a matching and a k-bounded star forest is polynomially solvable for any k ∈ ℕ ∪ \ ∞ \, answering another question by Campbell, Hörsch and Moore from the same paper.