The Almost-Disjoint 2-Path Decomposition Problem

Annika Thome, Matthias Walter

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 e…