Improving a fixed parameter tractability time bound for the shadow problem

✍ Scribed by Peter Heusch; Stefan Porschen; Ewald Speckenmeyer

• Book ID: 104147726
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 238 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00079-5

✦ Synopsis

Consider a forest of k trees and n nodes together with a (partial) function s mapping leaves of the trees to non-root nodes of other trees. Define the shadow of a leaf c to be the subtree rooted at sðcÞ: The shadow problem asks whether there is a set S of leaves exactly one from each tree such that none of these leaves lies in the shadow of another leaf in S: This graph theoretical problem as shown in Franco et al. (Discrete Appl. Math. 96 (1999) 89) is equivalent to the falsifiability problem for pure implicational Boolean formulas over n variables with k occurences of the constant false as introduced in: