A new parameterization of the shadow problem

Porschen, Stefan (2005) A new parameterization of the shadow problem.
Technical Report , 16 p.


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 .

Download: [img] Postscript
Download (282kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-501
Depositing User: Stefan Porschen
Date Deposited: 23 Nov 2005 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/501