Graph Parameters, Universal Obstructions, and WQO

We introduce the notion of a universal obstruction of a graph parameter with respect to some quasi-ordering relation on graphs. Universal obstructions may serve as a canonical obstruction characterization of the approximate behaviour of graph parameters. We provide an order-theoretic characterization of the finiteness of universal obstructions and, when this is the case, we present some algorithmic implications on the existence of fixed-parameter algorithms.