HEXAGONbeta

Fractional DAG treewidth controls DAG treewidth: profile reorientation and VC-dimension rounding

Primarily AI-generated textHuman understanding: some partscs.DM — Discrete Mathematicscs.DS — Data Structures and Algorithmsmath.CO — Combinatorics

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 15, 2026 / CC BY 4.0

Abstract

For a nonempty finite graph, let FF be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most 160F3ln⁡(16F)160F^3\ln(16F). This answers the boundedness question of Bressan, Lanzinger, and Roth. Reorienting the graph converts shattered source profiles into projective-plane obstructions, which bound their VC dimension by 5F25F^2. Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. M. Bressan, M. Lanzinger, and M. Roth, The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree , STOC 2023, pp. 542--552. Conference version (https://doi.org/10.1145/3564246.3585204). Full version: arXiv:2211.01905v1 (https://arxiv.org/abs/2211.01905v1), 2022.arXivDOI
  2. M. Bressan, Faster Algorithms for Counting Subgraphs in Sparse Graphs , Algorithmica 83 (2021), 2578--2605. doi:10.1007/s00453-021-00811-0 (https://doi.org/10.1007/s00453-021-00811-0). Full version: arXiv:1805.02089v5 (https://arxiv.org/abs/1805.02089v5).arXivDOI
  3. M. Grohe and D. Marx, Constraint Solving via Fractional Edge Covers , ACM Transactions on Algorithms 11 (1) (2014), Article 4. doi:10.1145/2636918 (https://doi.org/10.1145/2636918). arXiv:1711.04506 (https://arxiv.org/abs/1711.04506).arXivDOI
  4. G. Gottlob, M. Lanzinger, R. Pichler, and I. Razgon, Complexity Analysis of Generalized and Fractional Hypertree Decompositions , Journal of the ACM (2021). doi:10.1145/3457374 (https://doi.org/10.1145/3457374). Full version: arXiv:2002.05239v2 (https://arxiv.org/abs/2002.05239v2), 2020.arXivDOI
  5. D. Haussler and E. Welzl, Epsilon-Nets and Simplex Range Queries , Proceedings of the Second Annual Symposium on Computational Geometry (SoCG 1986), pp. 61--71. Conference version (https://doi.org/10.1145/10515.10522).DOI
  6. H. Brönnimann and M. T. Goodrich, Almost Optimal Set Covers in Finite VC-Dimension , Discrete & Computational Geometry 14 (1995), 463--479. doi:10.1007/BF02570718 (https://doi.org/10.1007/BF02570718).DOI
  7. N. Sauer, On the Density of Families of Sets , Journal of Combinatorial Theory, Series A 13 (1) (1972), 145--147. doi:10.1016/0097-3165(72)90019-2 (https://doi.org/10.1016/0097-3165(72)90019-2).DOI
  8. S. Shelah, A Combinatorial Problem; Stability and Order for Models and Theories in Infinitary Languages , Pacific Journal of Mathematics 41 (1) (1972), 247--261. doi:10.2140/pjm.1972.41.247 (https://doi.org/10.2140/pjm.1972.41.247).DOI
  9. B. Komarath, A. Kumar, and A. Pareek, Counting Patterns in Degenerate Graphs in Constant Space , arXiv:2511.04258v2 (https://arxiv.org/abs/2511.04258v2), 30 June 2026.arXiv
  10. D. Paul-Pena and C. Seshadhri, Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs , ICALP 2025, LIPIcs 334 , Article 124, pp. 124:1--124:18. Conference version (https://doi.org/10.4230/LIPIcs.ICALP.2025.124).DOI

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 15, 2026