"On Generalizations of the Shadow Independent Set Problem"
Technical report by Stefan Porschen, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Speckenmeyer
Preprint Key:	zaik2004-461
Keywords:	(relational) shadow pattern, directed acyclic graph, dynamic programming, fixed parameter tractability, forest, shadow independent set
MSC codes:	03B05, 05C69, 05C85
This technical report has 18 pages, was written in October 2002, it has not been published.
Abstract:	The {em shadow independent set problem (SIS)} being a new NP-complete problem in algorithmic graph theory was introduced in cite{Franco}. It considers a forest F of kin IN (rooted) trees and nin IN vertices. Further a function sigma is given mapping the set of all leaves into the set of all vertices of F. Defining the {em shadow} of a leaf ell as the subtree rooted at sigma(ell) SIS asks for the existence of a set S of leaves exactly one from each tree, such that no leaf of S is contained in the shadow of any leaf in S. In cite{Franco} the {em fixed parameter tractability (FPT)} of SIS has been shown by obtaining O(n^2k^k) as an upper bound for its computational complexity. Recently, a new FPT bound O(n^33^k) for SIS was obtained in cite{Porschen} by dynamic programming techniques. In the present paper FPT is investigated for several generalizations of SIS. First sigma is replaced by a binary relation Sigma assigning an arbitrary number r(ell)in IN of pointers to each leaf ell. Substituting F by a set of directed acyclic graphs yields a second (structural) generalization. We are able to obtain FPT bounds for these problems generalizing the techniques in cite{Porschen}, which cannot be achieved adapting the results in cite{Franco}.