A 5k-vertex kernel for P2-packing

Wenjun Li, Junjie Ye, Yixin Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review


The P 2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 2 Apr 2022


  • Crown decomposition
  • Kernelization algorithm
  • P2-packing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A 5k-vertex kernel for P2-packing'. Together they form a unique fingerprint.

Cite this