On Generalizations of the Shadow Independent Set Problem

Porschen, Stefan (2002) On Generalizations of the Shadow Independent Set Problem.
Technical Report , 18 p.


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}.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-461
Depositing User: Stefan Porschen
Date Deposited: 05 Apr 2007 00:00
Last Modified: 15 Aug 2011 12:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/461