A polynomial kernel for 3-leaf power deletion

Publication date 11 November 2019

Abstract: For a non-negative integer

e l l

, a graph

G

is an

e l l

-leaf power of a tree

T

if

V (G)

is equal to the set of leaves of

T

, and distinct vertices

v

and

w

of

G

are adjacent if and only if the distance between

v

and

w

in

T

is at most

e l l

. Given a graph

G

, 3-Leaf Power Deletion asks whether there is a set

S s u b s e t e q V (G)

of size at most

k

such that

G s e t m i n u s S

is a

3

-leaf power of some tree

T

. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance

(G, k)

to output an equivalent instance

(G^{'}, k^{'})

such that

k^{'} l e q k

and

G^{'}

has at most

O (k^{14})

vertices.

This page was built for publication: A polynomial kernel for $3$-leaf power deletion