Co-Decompositions and FO Model Checking
Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fibered products of small constituent parts. Co-decompositions are compressed representations of graphs or relational structures: the decomposed object can be exponentially larger than the space required to specify the co-decomposition. Our main contribution is an algorithmic meta-theorem for first order logic: given only a co-decomposition of a $σ$-structure $G$ with $b$ bags, each of size at most $w$ and an FO sentence $ϕ$, there is an algorithm which, without ever constructing or inspecting $G$, operates on the co-decomposition and determines whether $G \models ϕ$ in time $f_σ(w,|φ|)\cdot b$. We pair this algorithm with structural results on tree co-width, including its relationship to tree-width and a separation from twin-width. Furthermore, we characterize bounded path co-width using a graph grammar. In contrast to our logical meta-theorem, we prove that $(s,t)$-Path becomes NP-hard on co-decomposition inputs. These results demonstrate how categorical constructions can enable efficient computation on exponentially compressed structures.
- quotes — Co-Decompositions and FO Model Checking (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — summary: Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fibered products of small constituent parts. Co-decompositions are compressed representations of graphs or relational structures: the decomposed object can be exponentially larger than the space required to specify the co-decomposition. Our main contribution is an algorithmic meta-theorem for first order logic: given only a co-decomposition of a $σ$-structure $G$ with $b$ bags, each of size at most $w$ and an FO sentence $ϕ$, there is an algorithm which, without ever constructing or inspecting $G$, operates on the co-decomposition and determines whether $G \models ϕ$ in time $f_σ(w,|φ|)\cdot b$. We pair this algorithm with structural results on tree co-width, including its relationship to tree-width and a separation from twin-width. Furthermore, we characterize bounded path co-width using a graph grammar. In contrast to our logical meta-theorem, we prove that $(s,t)$-Path becomes NP-hard on co-decomposition inputs. These results demonstrate how categorical constructions can enable efficient computation on exponentially compressed structures. (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — url: https://arxiv.org/abs/2611.04658 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — source-subject: arxiv:2611.04658 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — source-edition: sha256:b79c71ecc7d75af343015a381198239481e3f883f1fd80850bf64945745e6ce6 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — source-metadata: {"subject":"arxiv:2611.04658","id":"2611.04658","url":"https://arxiv.org/abs/2611.04658","datestamp":"2026-11-04","status":"present","title":"Co-Decompositions and FO Model Checking","abstract":"Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fibered products of small constituent parts. Co-decompositions are compressed representations of graphs or relational structures: the decomposed object can be exponentially larger than the space required to specify the co-decomposition. Our main contribution is an algorithmic meta-theorem for first order logic: given only a co-decomposition of a $σ$-structure $G$ with $b$ bags, each of size at most $w$ and an FO sentence $ϕ$, there is an algorithm which, without ever constructing or inspecting $G$, operates on the co-decomposition and determines whether $G \\models ϕ$ in time $f_σ(w,|φ|)\\cdot b$. We pair this algorithm with structural results on tree co-width, including its relationship to tree-width and a separation from twin-width. Furthermore, we characterize bounded path co-width using a graph grammar. In contrast to our logical meta-theorem, we prove that $(s,t)$-Path becomes NP-hard on co-decomposition inputs. These results demonstrate how categorical constructions can enable efficient computation on exponentially compressed structures.","authors":["Benjamin Merlin Bumpus","Guilherme C. M. Gomes","Laura Larios-Jones","Will J. Turner"],"categories":["math.CO","math.CT"],"created":"2026-11-03","updated":"2026-11-04","articleLicense":"http://creativecommons.org/licenses/by-sa/4.0/","version":null,"editionDigest":"sha256:b79c71ecc7d75af343015a381198239481e3f883f1fd80850bf64945745e6ce6","sourceResponseAt":"2026-11-18T21:09:11Z","sourceDigest":"sha256:9463ef807009af84c66928c04f1b177905cda41c60c5b55e502ef901a90fca83"} (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)
- quotes — editorial-standing: source metadata; editorial acceptance pending (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.04658; status: unverified)