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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

Let integers r≥2 and d≥3 be fixed. Let Gd be the set of graphs with no induced path on d vertices. We study the problem of packing k vertex-disjoint copies of K1,r (k≥2) into a graph G from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph G∈Gd can be reduced, in polynomial time, to a graph G'∈Gd with O(k) vertices such that G has at least k vertex-disjoint copies of K1,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≥2.

Original languageEnglish
JournalInformation Processing Letters
Volume116
Issue number6
Pages (from-to)433 - 436
ISSN0020-0190
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Fixed-parameter tractability
  • Graph algorithms
  • Kernel
  • Packing
  • Stars

Fingerprint

Dive into the research topics of 'Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths'. Together they form a unique fingerprint.

Cite this