Abstract: |
The shadow problem (SIS) gets as input a forest F,
and a map that assigns
subtrees, called shadows, to leaves of F. SIS asks whether there
exists a set of |F| leaves, one from each tree,
such that no leaf lies in the shadow of another.
Usually SIS is considered as a parameterized problem with parameter k
bounding the cardinality of F, for which some fixed-parameter
tractability time bounds have been
proven.
In this paper, we propose a different parameterization of SIS using two
independent
parameters, namely k as above, and s bounding the shadow size.
We provide a kernelization w.r.t. the new parameterization,
and prove a fixed-parameter tractability bound of
O(kcdot n^2+p(k,s)3^k) where p is a polynomial in the parameters k,s.
|
