Graph Parameters, Universal Obstructions, and WQO

Abstract

We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $⩽$ on graphs. At the center of this framework lies the concept of a $⩽$-parametric graph: a non $⩽$-decreasing sequence $\mathcal{G}=⟨{\mathcal{G}}_t{⟩}_{t\in \mathbb{N}}$ of graphs indexed by non-negative integers. Parametric graphs allow us to define combinatorial objects that capture the approximate behaviour of graph parameters. A finite set $\mathfrak{G}$ of $⩽$-parametric graphs is a $⩽$-universal obstruction for a parameter $\mathsf{p}$ if there exists a function $f:\mathbb{N}\to \mathbb{N}$ such that, for every $k\in \mathbb{N}$ and every graph $G$, 1) if $\mathsf{p}(G)\le k$, then for every $\mathcal{G}\in \mathfrak{G},$ ${\mathcal{G}}_{f(k)}/⩽G$, and 2) if for every $\mathcal{G}\in \mathfrak{G},$ ${\mathcal{G}}_k/⩽G$, then $\mathsf{p}(G)\le f(k).$ To solidify our point of view, we identify sufficient order-theoretic conditions that guarantee the existence of universal obstructions and in this case we examine algorithmic implications on the existence of fixed-parameter tractable algorithms. Our parametric framework has further implications related to finite obstruction characterizations of properties of graph classes. A $⩽$-class property is defined as any set of $⩽$-closed graph classes that is closed under set inclusion. By combining our parametric framework with established results from order theory, we derive a precise order-theoretic characterization that ensures $⩽$-class properties can be described in terms of the exclusion of a finite set of $⩽$-parametric graphs.