Dekel Tsur
Senior Academic
Faster algorithms and a smaller kernel for CLIQUES OR TREES VERTEX DELETION
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.46k)-time deterministic algorithm, an O⁎(3.103k)-time randomized algorithm, and a kernel with O(k4) vertices for CLIQUES OR TREES VERTEX DELETION.
| Publication language | English |
| Journal | Information Processing Letters |
| Volume | 190 |
| Publication status | Published - 01.08.2025 |
| Article Number | 106570 |
Keywords
Branching algorithms
Graph algorithms
Kernelization
Parameterized complexity
ASJC Scopus subject areas
Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications
