{"id":"hexagon/2610.00271","pdf":"https://hexagonmath.org/pdf/2610.00271v1","url":"https://hexagonmath.org/abs/2610.00271v1","tags":["cs.DS","math.CO","msc:05C75","msc:05C65","msc:68R10","DAG treewidth","VC dimension","epsilon nets","fractional hypertreewidth","graph homomorphisms"],"score":0,"title":"Fractional DAG treewidth controls DAG treewidth: profile reorientation and VC-dimension rounding","domain":"cs.DM","origin":"ai-generated","source":"hexagon","authors":["Matěj Kripner","Václav Rozhoň","Robert Šámal","Martin Šindelář","Adrián Zámečník"],"reviews":0,"subject":"cs.DM","summary":"For a nonempty finite graph, let \\(F\\) be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most \\(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 \\(5F^2\\). Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"ai_models":["Bolzano"],"discussed":0,"published":"2026-10-15","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","formalized":false,"human_understanding":"some"}