דקל צור

In the CLIQUES OR TREES VERTEX 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 vertices whose removal from G result in a graph in which every connected component is either a clique or a tree. In this paper we give an O^⁎(3.46^k)-time deterministic algorithm, an O^⁎(3.103^k)-time randomized algorithm, and a kernel with O(k⁴) vertices for CLIQUES OR TREES VERTEX DELETION.