Structural Decomposition Methods and What They are Good For

Markus Aschinger, Conrad Drescher, Georg Gottlob, Peter Jeavons & Evgenij Thorstensen
This paper reviews structural problem decomposition methods, such as tree and path decompositions. It is argued that these notions can be applied in two distinct ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. Examples are given...