A $(2+\epsilon)k$-vertex kernel for Edge Triangle Deletion Problem

Abstract

The Edge Triangle Deletion problem asks whether we can delete at most $k$ edges from the input graph such that there is no triangle in the remaining graph. This problem is NP-hard and has been well studied in the parameterized complexity. A vertex kernel of size $6k$ was proved about 10 years ago. Last week, Zimo Sheng gave a $3k$ kernel for ETD by finding an approximate solution with some analysis. Today, we show that for any fixed $\epsilon > 0$ a polynomial-time algorithm can reduce the input instance to an equivalent instance of at most $(2+\epsilon)k$ vertices. The linear-vertex kernel is obtained using an extended crown decomposition combined with linear programming and other techniques.