Graph Parameters, Universal Obstructions, and WQO
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912130777743360 |
|---|---|
| author | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. |
| author_facet | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. |
| contents | We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leqslant$ on graphs. At the center of this framework lies the concept of a $\leqslant$-parametric graph: a non $\leqslant$-decreasing sequence $\mathscr{G} = \langle \mathscr{G}_{t} \rangle_{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 $\leqslant$-parametric graphs is a $\leqslant$-universal obstruction for a parameter $\mathsf{p}$ if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every $k \in \mathbb{N}$ and every graph $G$, 1) if $\mathsf{p}(G) \leq k$, then for every $\mathscr{G} \in \mathfrak{G},$ $\mathscr{G}_{f(k)} \not\leqslant G$, and 2) if for every $\mathscr{G} \in \mathfrak{G},$ $\mathscr{G}_{k} \not\leqslant G$, then $\mathsf{p}(G) \leq 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 $\leqslant$-class property is defined as any set of $\leqslant$-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 $\leqslant$-class properties can be described in terms of the exclusion of a finite set of $\leqslant$-parametric graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_03688 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Graph Parameters, Universal Obstructions, and WQO Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Combinatorics Discrete Mathematics 06A07, 05C83, 05C85 G.2.1; F.2.2; G.2.2 We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leqslant$ on graphs. At the center of this framework lies the concept of a $\leqslant$-parametric graph: a non $\leqslant$-decreasing sequence $\mathscr{G} = \langle \mathscr{G}_{t} \rangle_{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 $\leqslant$-parametric graphs is a $\leqslant$-universal obstruction for a parameter $\mathsf{p}$ if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every $k \in \mathbb{N}$ and every graph $G$, 1) if $\mathsf{p}(G) \leq k$, then for every $\mathscr{G} \in \mathfrak{G},$ $\mathscr{G}_{f(k)} \not\leqslant G$, and 2) if for every $\mathscr{G} \in \mathfrak{G},$ $\mathscr{G}_{k} \not\leqslant G$, then $\mathsf{p}(G) \leq 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 $\leqslant$-class property is defined as any set of $\leqslant$-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 $\leqslant$-class properties can be described in terms of the exclusion of a finite set of $\leqslant$-parametric graphs. |
| title | Graph Parameters, Universal Obstructions, and WQO |
| topic | Combinatorics Discrete Mathematics 06A07, 05C83, 05C85 G.2.1; F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2304.03688 |