2019/07/10 by Annika Thome, Thome, Annika, Matthias Walter +1
Computer Science · #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1907.04906
openalex publication_date 2019/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of decomposing a given (di)graph into paths of length 2 with the additional restriction that no two such paths may have more than one vertex in common. We establish its NP-hardness by a reduction from 3-SAT, characterize (di)graph classes for which the problem can be be reduced to the Stable-set problem on claw-free graphs and describe a dynamic program for solving it for series-parallel digraphs.