A linear vertex kernel for the Paw edge covering problem
One important class of problems in graph theory involves investigating whether it is possible to delete at most k edges from a graph in such a way that the remaining graph does not contain a certain subgraph structure H.The case where the subgraph H is a connected graph with at most 4 vertices has been widely studied.In this paper,we specifically consider the case where H is a Paw graph(a triangle with one vertex incident to an additional edge).The corresponding problem is called the Paw edge covering problem(also known as the {Paw,Diamond,K4}-free edge deletion problem).In this paper,by using two new variants of crown decompositions,we show that the Paw edge covering problem has a kernel of 32k vertices,which is the first linear-size vertex kernel for this problem.
NETL
NSTL
万方数据
