2023/08/31 by Zimo Sheng, Sheng, Zimo, Mingyu Xiao +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2308.16515
openalex publication_date 2023/08/31 · openalex created_date 2023/09/03 · openalex updated_date 2026/07/28
Edge Triangle Packing and Edge Triangle Covering are dual problems extensively studied in the field of parameterized complexity. Given a graph G and an integer k, Edge Triangle Packing seeks to determine whether there exists a set of at least k edge-disjoint triangles in G, while Edge Triangle Covering aims to find out whether there exists a set of at most k edges that intersects all triangles in G. Previous research has shown that Edge Triangle Packing has a kernel of (3+ε)k vertices, while Edge Triangle Covering has a kernel of 6k vertices. In this paper, we show that the two problems allow kernels of 3k vertices, improving all previous results. A significant contribution of our work is the utilization of a novel discharging method for analyzing kernel size, which exhibits potential for analyzing other kernel algorithms.