Dekel Tsur
Senior Academic
Kernel for Kt-FREE EDGE DELETION
In the Kt-FREE EDGE DELETION problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges of G whose removal results in a graph with no clique of size t. In this paper we give a kernel to this problem with O(kt−1) vertices and edges.
| Publication language | English |
| Journal | Information Processing Letters |
| Volume | 167 |
| Publication status | Published - 01.04.2021 |
| Article Number | 106082 |
Keywords
Graph algorithms
Kernelization
Parameterized complexity
ASJC Scopus subject areas
Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications
