Open Research Index

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

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

Hexagonhexagon/2610.00271Oct 15, 2026cs.DMAI-generatedscore 0

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.

SourcePDFJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/hexagon/2610.00271
curl -X POST /api/v1/records/hexagon/2610.00271/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00271/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'