Algorithms and Logic Group

Zimo Sheng: Improved Kernels for Edge Triangle Covering Problem

Speaker:

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

Time:

  • 16:20-17:20 (Time in Beijing)
  • March 31, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

Kernelization is a concept of data preprocessing which is possible to derive upper and lower bounds on sizes of reduced instance. Edge Triangle Covering is an important NP-hard problem that has been well studied in exact and parameterized complexity.In this paper, we study kernelization of the Edge Triangle Covering problem, which is to check whether a given graph has a edge-disjoint covering size of at most k. We prove a kernel of $3k$ vertices, improving the previous bound of $6k$.