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

Florian Barbero, Gregory Gutin, Mark Jones, Bin Sheng, Anders Yeo

Research output: Contribution to journalArticlepeer-review

60 Downloads (Pure)


Let integers $r\ge 2$ and $d\ge 3$ be fixed. Let ${\cal G}_d$ be the set of graphs with no induced path on $d$ vertices. We study the problem of packing $k$ vertex-disjoint copies of $K_{1,r}$ ($k\ge 2$) into a graph $G$ from parameterized preprocessing, i.e., kernelization, point of view.
We show that every graph $G\in {\cal G}_d$ can be reduced, in polynomial time, to a graph $G'\in {\cal G}_d$ with $O(k)$ vertices such that $G$ has at least $k$ vertex-disjoint copies of $K_{1,r}$ if and only if $G'$ has. Such a result is known for arbitrary graphs $G$ when $r=2$ and we conjecture that it holds for every $r\ge 2$.
Original languageEnglish
Pages (from-to)433–436
Number of pages4
JournalInformation Processing Letters
Issue number6
Early online date26 Jan 2016
Publication statusPublished - Jun 2016

Cite this