A planning problem is k- dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P ( k ), the class of k- dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P ( k ) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P (2) and P (3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P ( k ) is polynomial.