# On Generalizations of the Shadow Independent Set Problem

Porschen, Stefan
(2002)
*On Generalizations of the Shadow Independent Set Problem.*

Technical Report
, 18 p.

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

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 |