A fa dekompozíció a kényszerkielégítési problémák egyik absztraktabb megoldási módja. Ennek alapján az eredeti problémát egy fára bontjuk, melyek csomópontja egy kisebb kényszerkielégítési problémát tartalmaz. A fa csomópontjai össze vannak kötve, és ezen élek is egy-egy kényszert fogalmaznak meg. A dekompozíció annál hatásosabb minél kisebb részproblémára tudjuk felbontani az eredeti problémát.