Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths

•Packing r-stars in a graph with no long induced paths.•Parameter is the number k of r-stars.•Linear-vertex kernel.•Conjecture for the general case.

Let integers r≥2r≥2 and d≥3d≥3 be fixed. Let GdGd be the set of graphs with no induced path on d vertices. We study the problem of packing k   vertex-disjoint copies of K1,rK1,r (k≥2k≥2) into a graph G   from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph G∈GdG∈Gd can be reduced, in polynomial time, to a graph G′∈GdG′∈Gd with O(k)O(k) vertices such that G has at least k   vertex-disjoint copies of K1,rK1,r if and only if G′G′ has. Such a result is known for arbitrary graphs G   when r=2r=2 and we conjecture that it holds for every r≥2r≥2.