Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths. / Barbero, Florian; Gutin, Gregory; Jones, Mark; Sheng, Bin; Yeo, Anders.

In: Information Processing Letters, Vol. 116, No. 6, 06.2016, p. 433–436.

Research output: Contribution to journalArticle

Published

Documents

Links

Abstract

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
Volume116
Issue number6
Early online date26 Jan 2016
DOIs
Publication statusPublished - Jun 2016
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26003649