On generalizations of the shadow independent set problem

The shadow independent set (SIS) problem being a new NP-complete problem in algorithmic graph theory was introduced in [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.]. It considers a forest F   of k∈Nk∈N (rooted) trees and n∈Nn∈N vertices. Further, a function σσ is given mapping the set of all leaves into the set of all vertices of F. Defining the shadow   of a leaf ℓℓ as the subtree rooted at σ(ℓ)σ(ℓ) 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 [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.] the fixed parameter tractability   (FPT) of SIS has been shown by obtaining O(n2kk)O(n2kk) as an upper bound for its computational complexity. Recently, a new FPT bound O(n33k)O(n33k) for SIS was found in [P. Heusch, S. Porschen, E. Speckenmeyer, Improving a fixed parameter tractability time bound for the shadow problem, J. Comput. System Sci. 67 (2003) 772–788.] by dynamic programming techniques. In the present paper FPT is investigated for several generalizations of SIS. First, σσ is replaced by a binary relation ΣΣ assigning an arbitrary number of vertices to each leaf. Substituting F by a set of directed acyclic graphs yields a second (structural) generalization. We prove FPT bounds for these problems by generalizing the techniques in [P. Heusch, S. Porschen, E. Speckenmeyer, Improving a fixed parameter tractability time bound for the shadow problem, J. Comput. System Sci. 67 (2003) 772–788.], which cannot be achieved adapting the results in [J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, R.P. Swaminathan, An algorithm for the class of pure implicational formulas, Discrete Appl. Math. 96 (1999) 89–106.].