Dominance constraints are conjunctions of literals of the formXi⊳(Xj1,..., Xjk),

Abstract. Dominance constraints logically describe trees in terms of their adjacency and dominance, i.e. reachability, relation. They have im-portant applications in computational linguistics. Unfortunately, the sat-isfiability problem of dominance constraints is NP-complete. In this extended abstract we describe efficient algorithms for natural subclasses of dominance constraints [BDNM03]. The instances of these subclasses are more appropriately formulated as configuration problems of so called dominance graphs. We show that for one particular subclass satisfiability can be characterized in terms of forbidden subgraphs in the corresponding dominance graph [ADKMNT]. These forbidden subgraphs can be found in linear time [Th04]