Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations.

In the ▪- Free Edge Deletion problem (CDFED), we are given a graph G and an integer k > 0 , and the question is whether there are at most k edges whose deletion results in a graph without claws and diamonds as induced subgraphs. Based on some refined observations, we propose a kernel of O (k 3) vertices and O (k 4) edges, significantly improving the previous kernel of O (k 12) vertices and O (k 24) edges. In addition, we derive an O ⁎ (3.792 k) -time algorithm for CDFED. [ABSTRACT FROM AUTHOR]