{"id":"arxiv/2602.12925","url":"https://arxiv.org/abs/2602.12925","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Optimal Path Partitions in Subcubic and Almost-subcubic Graphs","domain":"cs.DS","source":"arxiv","authors":["Tomáš Masařík","Michał Włodarczyk","Mehmet Akif Yıldız"],"reviews":0,"subject":"cs.DS","summary":"We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinatorics. Regarding the complexity of partitioning a graph optimally, Peroché [Discret. Appl. Math., 1984] proved that it is NP-hard already on graphs of maximum degree four, even when we only ask if two paths suffice. We show that the problem is solvable in polynomial time on subcubic graphs and then we present an efficient algorithm for ``almost-subcubic'' graphs. Precisely, we prove that the problem is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}