Speaker:
Yuxi Liu (University of Electronic Science and Technology of China)
Time:
- 16:20-17:20 (Time in Beijing)
- April 7, 2023 (Friday)
Venue:
518, Research Building 4
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.