Packing paths: Recycling saves time
We consider packing problems in graphs under a parameterized perspective. Starting from a maximal path packing P P of size j j we use extremal arguments for determining how many vertices of P P appear in a path packing of size j+1 j + 1 . Generally, one can re-use 2j 2 j vertices of j j paths of length three, four and five. This is improved to 3j 3 j , 2.5j 2.5 j and 3j 3 j vertices.
packings graphs parameterized algorithms extremal graph theory