Kernels for Planar Vertex-Disjoint Triangle Packing

Speaker:

Zimo Sheng (University of Electronic and Science Technology of China)

Time:

10:00-12:00 (Time in Beijing)
14:00-16:00 (Time in Auckland)
May 14, 2021 (Friday)

VooVmeeting:

Link: https://meeting.tencent.com/s/oLdo3h9nEQlW

ID: 655 461 488

Venue:

Main Building

Abstract:

Triangle Packing is an important class of NP-hard problem. In this paper, we study Parameterized Planar Vertex-Disjoint Triangle Packing problem, which is to find $k$ vertex-disjoint triangles in a given planar graph. The current best kernel for this problem is $732k$ . In this paper we will improve the result to $150k$ by giving new reduction rules and more careful analyze.