Solving planning domains with polytree causal graphs is NP-complete

It is well known that the planning problem (namely, the probl em of obtaining a valid sequence of transformations that moves a sys tem from an initial state to a goal state) is intractable in general [3]. However, it is widely believed that many real-life problems have a particu lar structure, and that by exploiting this structure general planners will be able to efficiently handle more meaningful problems. One of the most fruitful tools researchers have been using to characterize structure in planning problems is the so called causal graph ([6]). In short, the causal graph of a problem instance is a graph that c aptures the degree of interdependence among the state variables of the p roblem.The causal graph has been used both as a tool for describing tract able subclasses of planning problems (e.g., [7], [2], [4]) and as a ke y property which algorithms that adress the general planning problem take in to consideration [5]. In the present work we show that solving planning domains whe re the causal graph is a polytree (that is, the underlying undir ected graph is acyclic) is NP-complete, even if we restrict to domains wi th binary variables and unary operators. This result closes the compl exity gap that appears in [4], where it is shown that plan existence is NP-co mplete for planning domains with singly connected causal graphs, and t hat plan generation is polynomial for planning domains with polytre e causal graphs of bounded indegree. Additionally, it is known that solving unary operator plann ing problems on binary variables is essentially equivalent to solvi ng dominance queries for binary-valued CP-nets (see [1]). Under this ref ormulation the causal graph becomes the CP-net, so the present work also sho ws that dominance testing for binary-valued polytree CP-nets is NP -complete.