\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=1in]{geometry} \usepackage{microtype} \usepackage{hyperref} \hypersetup{ colorlinks=true, linkcolor=blue, citecolor=blue, urlcolor=blue, pdftitle={Fractional DAG treewidth controls DAG treewidth}, pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník} } \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \DeclareMathOperator{\Acyc}{Acyc} \DeclareMathOperator{\dtw}{dtw} \DeclareMathOperator{\fdtw}{fdtw} \DeclareMathOperator{\htw}{htw} \DeclareMathOperator{\fhtw}{fhtw} \DeclareMathOperator{\VCdim}{VCdim} \newcommand{\cR}{\mathcal R} \newcommand{\cA}{\mathcal A} \newcommand{\cF}{\mathcal F} \newcommand{\cL}{\mathcal L} \newcommand{\vecH}{\vec H} \title{Fractional DAG treewidth controls DAG treewidth:\\ profile reorientation and VC-dimension rounding\thanks{This work was produced within the Bolzano project (\url{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.}} \author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em] Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k} \date{} \usepackage{lmodern} \usepackage{xcolor} % Collection typography. \geometry{a4paper,hmargin=23mm,vmargin=25mm} \definecolor{BolzanoInk}{HTML}{24445C} \hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk, urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}} \urlstyle{same} \setlength{\emergencystretch}{1em} \let\BolzanoBibliography\thebibliography \renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\small\raggedright} \begin{document} \maketitle \begin{abstract} 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. \end{abstract} \section{Introduction} \subsection{Background and the source problem} A source of a directed acyclic graph reaches a region that can be explored by following outgoing edges. When the host graph has bounded outdegree, this makes sources useful units for organizing a homomorphism-counting algorithm. A decomposition records which source-generated regions must be coordinated at each step. Bressan's DAG tree decompositions formalize this principle for sparse-host pattern counting \cite[Defs.~2, 3, 6 and Thm.~9]{Bressan}. Bressan, Lanzinger, and Roth express the corresponding directed problem as a counting constraint-satisfaction problem whose exponent is governed by fractional hypertreewidth \cite[Sec.~3.4 and Thm.~42]{BLR}. The two width notions measure how economically each decomposition bag can be covered. An integral cover chooses source-reachability regions; a fractional cover may distribute unit coverage among several sources. Write \(\cR(\vecH)\) for the hypergraph of these regions in an acyclic orientation \(\vecH\) of an undirected graph \(H\). Following the comparison in \cite[Sec.~3.4]{BLR}, this paper uses \[ \dtw(H)=\max_{\vecH\in\Acyc(H)}\htw(\cR(\vecH)), \qquad \fdtw(H)=\max_{\vecH\in\Acyc(H)}\fhtw(\cR(\vecH)), \] where \(\htw\) denotes \emph{generalized} hypertreewidth, with no additional condition on guards. Precise definitions appear in Section~\ref{sec:definitions}. The maximum over orientations is essential: the comparison concerns every acyclic orientation of the same underlying graph. There is a notation distinction within the DAG-treewidth literature. The parameter \(\dtw\) here is the homomorphism parameter called \(\tau_1\) in \cite[Def.~6]{Bressan}. That definition also introduces \(\tau_2\), maximizing over vertex identifications, and \(\tau_3\), additionally maximizing over edge additions, for other counting tasks. The present comparison is about \(\tau_1\) and its fractional analogue; it does not identify these three parameters. Bressan, Lanzinger, and Roth explicitly ask whether unbounded DAG treewidth and unbounded fractional DAG treewidth are equivalent \cite[Sec.~3.4, p.~10]{BLR}. Equivalently: \begin{question}[{\cite[Sec.~3.4]{BLR}}]\label{question:source} For every graph class \(\mathcal C\), is \[ \sup_{H\in\mathcal C}\dtw(H)<\infty \quad\Longleftrightarrow\quad \sup_{H\in\mathcal C}\fdtw(H)<\infty? \] \end{question} For arbitrary hypergraphs, the analogous assertion is false. Grohe and Marx give a family with fractional hypertreewidth at most two and unbounded generalized hypertreewidth \cite[Example~4.2]{GM}. Thus a comparison between the two widths of one unrestricted hypergraph cannot settle Question~\ref{question:source}. A graph supplies an entire family of reachability hypergraphs, coupled by reorientations, and this extra structure is what the proof uses. \subsection{Contribution} For every nonempty finite graph \(H\), the main bound is \[ \fdtw(H)\le\dtw(H)\le 160\,\fdtw(H)^3\ln\!\bigl(16\fdtw(H)\bigr). \] Consequently, the integral and fractional parameters are bounded on exactly the same graph classes. The proof has three parts. \begin{enumerate} \item The \emph{source profile} of a vertex is the set of sources that reach it. Covering a bag by reachability regions is equivalent to hitting its profiles (Lemma~\ref{lem:duality}). Given a set \(Q\) of sources, Lemma~\ref{lem:reorient} constructs another acyclic orientation of the same graph in which every relevant profile is exactly its original trace on \(Q\). \item If many sources are shattered by the profile family, the reorientation exposes the lines of a finite projective plane as exact profiles. Pairwise intersections force the associated vertices into one decomposition bag, and a counting argument makes its fractional cover expensive (Lemma~\ref{lem:incidence}). Writing \(F=\fdtw(H)\), Theorem~\ref{thm:vc} deduces \(\VCdim(\cA_{\vecH})<5F^2\) for every orientation. \item The classical epsilon-net method gives a transversal of size at most \(32dC\ln(16C)\) from a fractional transversal of weight \(C\) in VC dimension \(d\) (Theorem~\ref{thm:epsilon-net}, with explicit constants and proof). Applying it to the profiles of each bag proves Theorem~\ref{thm:main} and the class-level equivalence in Corollary~\ref{cor:equivalence}. \end{enumerate} The central point is the contrapositive of the second step. A complicated profile system cannot remain fractionally inexpensive under \emph{all} reorientations: some orientation exhibits a large fractional obstruction. Once profile complexity is bounded, the rounding step is standard. Generalized hypertreewidth permits guards to be chosen independently at different bags, so the tree and its bags remain unchanged. Neither an equality between the two widths nor an optimal numerical dependence on \(F\) is asserted. \subsection{Related work} The combinatorial ingredients of the rounding argument are classical. The Sauer--Shelah bound controls the number of traces of a set system \cite{Sauer,Shelah}; Haussler and Welzl use this bound and double sampling to obtain small epsilon-nets \cite{HW}. Br\"onnimann and Goodrich develop the corresponding algorithmic connection to set cover in finite VC dimension \cite{BG}. Theorem~\ref{thm:epsilon-net} supplies a finite weighted formulation and constants for the present application, rather than a new epsilon-net principle. In the hypertreewidth setting, Gottlob, Lanzinger, Pichler, and Razgon already use VC dimension to bound integral covering numbers in terms of fractional covering numbers, then replace the guards of a fractional decomposition while keeping its bags \cite[proof of Thm.~7.8]{GLPR}. Their argument shows why a suitable VC-dimension bound would suffice here. The additional structural step is to obtain such a bound for source profiles from the maximum fractional width over all orientations, using exact-profile reorientation and projective-plane incidence. Finer counting exponents are studied by Paul-Pena and Seshadhri: for every fixed pattern with at most nine vertices, they obtain \(\widetilde O(n^{5/3})\) time on bounded-degeneracy hosts \cite[Thm.~1.1]{PS}. This is a quantitative algorithmic improvement for small patterns, whereas Question~\ref{question:source} concerns uniform boundedness over graph classes of arbitrary pattern size. Recent work by Komarath, Kumar, and Pareek studies constant-space pattern counting through DAG treedepth, giving a homomorphism-counting algorithm whose exponent depends on that parameter \cite[Thm.~1]{KKP}. This addresses a space constraint and a different decomposition parameter. The present theorem is a structural comparison of the integral and fractional homomorphism widths in \cite[Sec.~3.4]{BLR}; it does not itself give a complete complexity classification or an optimal decomposition algorithm. \section{Reachability width and source profiles}\label{sec:definitions} \subsection{Definitions} All graphs and hypergraphs are finite. Let \(H\) be an undirected graph and let \(\Acyc(H)\) be the set of orientations of all edges of \(H\) that produce a directed acyclic graph. For \(\vecH\in\Acyc(H)\), write \(S(\vecH)\) for its sources and \(R_{\vecH}(s)\) for the vertices reachable from \(s\), including \(s\) itself. \begin{definition}[reachability hypergraph; {\cite[Def.~16]{BLR}}]\label{def:reachability} The reachability hypergraph of an acyclic orientation \(\vecH\) is \[ \cR(\vecH)= \bigl(V(H),\{R_{\vecH}(s):s\in S(\vecH)\}\bigr). \] \end{definition} For a hypergraph \(\mathcal H=(V,E)\) and \(X\subseteq V\), let \(\rho_{\mathcal H}(X)\) be the minimum number of hyperedges whose union contains \(X\). A fractional edge cover of \(X\) is a function \(\gamma:E\to[0,\infty)\) such that \[ \sum_{e\ni v}\gamma(e)\ge1\qquad(v\in X), \] and \(\rho^*_{\mathcal H}(X)\) is its minimum total weight. \begin{definition}[{\cite[Defs.~19--21]{BLR}}] \label{def:widths} A tree decomposition of \(\mathcal H\) is a tree \(T\) with bags \((B_t)_{t\in V(T)}\) such that \begin{enumerate} \item the bags cover \(V\); \item every hyperedge is contained in a bag; \item for each \(v\in V\), the nodes \(t\) with \(v\in B_t\) induce a connected subtree of \(T\). \end{enumerate} The generalized and fractional hypertreewidths are \[ \htw(\mathcal H)= \min_{(T,B)} \max_{t\in V(T)}\rho_{\mathcal H}(B_t), \qquad \fhtw(\mathcal H)= \min_{(T,B)} \max_{t\in V(T)}\rho^*_{\mathcal H}(B_t). \] \end{definition} Define \[ \dtw(H)=\max_{\vecH\in\Acyc(H)} \htw(\cR(\vecH)),\qquad \fdtw(H)=\max_{\vecH\in\Acyc(H)} \fhtw(\cR(\vecH)). \tag{2.1}\label{eq:dag-widths} \] For the null graph, both quantities are zero under the empty decomposition convention. For a fixed orientation \(\vecH\), associate to every vertex its \emph{source profile} \[ \sigma_{\vecH}(v)= \{s\in S(\vecH):v\in R_{\vecH}(s)\}. \tag{2.2}\label{eq:profile} \] Every profile is nonempty: following incoming edges backward from \(v\) must terminate at a source because the orientation is finite and acyclic. For \(X\subseteq V(H)\), let \[ \cA_{\vecH}(X)= \{\sigma_{\vecH}(v):v\in X\}, \] viewed as a family of nonempty subsets of the ground set \(S(\vecH)\). \subsection{Cover--transversal duality} For a family \(\cF\) of subsets of a finite ground set, a transversal is a set meeting every member of \(\cF\). Write \(\tau(\cF)\) for the minimum transversal size. A fractional transversal assigns nonnegative weights \(x_a\) to ground elements so that \(\sum_{a\in R}x_a\ge1\) for every \(R\in\cF\); its minimum total weight is \(\tau^*(\cF)\). \begin{lemma}\label{lem:duality} For every \(X\subseteq V(H)\), \[ \rho_{\cR(\vecH)}(X)=\tau(\cA_{\vecH}(X)), \qquad \rho^*_{\cR(\vecH)}(X)=\tau^*(\cA_{\vecH}(X)). \tag{2.3}\label{eq:cover-duality} \] \end{lemma} \begin{proof} The reachability hyperedges are uniquely indexed by sources. Indeed, if \(s\ne s'\) are sources, then \(s\in R_{\vecH}(s)\), whereas \(s\notin R_{\vecH}(s')\), because a nontrivial path ending at \(s\) would give \(s\) an incoming edge. A source set \(T\subseteq S(\vecH)\) indexes reachability edges covering \(X\) exactly when, for every \(v\in X\), some \(s\in T\) reaches \(v\). By \eqref{eq:profile}, this is equivalent to \(T\cap\sigma_{\vecH}(v)\ne\varnothing\) for every \(v\in X\), which is the transversal condition. Likewise, source weights \((\gamma_s)\) fractionally cover \(X\) exactly when \[ \sum_{s\in\sigma_{\vecH}(v)}\gamma_s\ge1 \qquad(v\in X). \] These are the fractional-transversal constraints with the same objective \(\sum_s\gamma_s\), proving both equalities. \end{proof} \section{Reorientation and profile complexity} \subsection{Cliques forced into decomposition bags} The primal graph of a hypergraph has the same vertex set, with two vertices adjacent when some hyperedge contains both. \begin{lemma}[subtree Helly argument]\label{lem:clique} Every clique in the primal graph of a hypergraph is contained in a bag of every tree decomposition of that hypergraph. \end{lemma} \begin{proof} Let \((T,(B_t))\) be a tree decomposition and let \(K\) be a primal clique. For \(v\in K\), the nodes \[ T_v=\{t\in V(T):v\in B_t\} \] form a nonempty connected subtree. If \(u,v\in K\), a hyperedge contains both and is itself contained in a bag, so \(T_u\cap T_v\ne\varnothing\). For completeness, root \(T\). In each \(T_v\), select the node nearest the root, and choose \(T_w\) whose selected node \(a_w\) has maximum depth. For any \(v\), choose \(x\in T_v\cap T_w\). The selected nodes \(a_v,a_w\) both lie on the root--\(x\) path; maximality of the depth of \(a_w\) puts \(a_w\) between \(a_v\) and \(x\). Since \(T_v\) is connected and contains \(a_v,x\), it contains \(a_w\). Hence \(a_w\in\bigcap_{v\in K}T_v\), and the bag \(B_{a_w}\) contains \(K\). \end{proof} \subsection{Exact profile restriction} The following lemma is the step that has no counterpart for one unrelated hypergraph. It uses a second acyclic orientation of the same underlying graph. \begin{lemma}[profile restriction by reorientation] \label{lem:reorient} Let \(\vecH\) be an acyclic orientation of \(H\), let \(Q\subseteq S(\vecH)\), and put \[ U=\bigcup_{q\in Q}R_{\vecH}(q),\qquad W=V(H)\setminus U. \] There is an acyclic orientation \(\vecH_Q\) of \(H\) such that \begin{enumerate} \item \(\vecH_Q[U]=\vecH[U]\); \item every edge between \(U\) and \(W\) points from \(U\) to \(W\); \item the sources of \(\vecH_Q\) in \(U\) are exactly \(Q\); \item no source in \(W\) reaches a vertex of \(U\); \item for every \(v\in U\), \[ \sigma_{\vecH_Q}(v)=\sigma_{\vecH}(v)\cap Q. \tag{3.1}\label{eq:trace} \] \end{enumerate} \end{lemma} \begin{proof} Retain every orientation inside \(U\), orient \(H[W]\) acyclically according to any total order on \(W\), and direct every cut edge from \(U\) to \(W\). There is no directed cycle within either side, and a cycle crossing the cut could not return from \(W\) to \(U\). Thus \(\vecH_Q\) is acyclic. Every \(q\in Q\) remains a source: it had no incoming edge in \(\vecH\), and all cut edges now point outward. If \(u\in U\setminus Q\), some \(q\in Q\) has a directed path to \(u\) in \(\vecH\). That entire path lies in \(U\), so its retained last edge is incoming at \(u\). Hence the sources in \(U\) are exactly \(Q\). The cut orientation prevents every directed path from \(W\) into \(U\), proving the fourth assertion. Fix \(q\in Q\) and \(v\in U\). Every old \(q\)-to-\(v\) path lies in \(U\) and is retained. Conversely, a new \(q\)-to-\(v\) path cannot leave \(U\), because it could not return, and the orientation in \(U\) is unchanged. Thus \(q\) reaches \(v\) in the new orientation exactly when it did in the old one. Together with the description of all new sources that can reach \(U\), this proves \eqref{eq:trace}. \end{proof} \subsection{An incidence obstruction} Recall that a set \(Q\) is shattered by a family \(\cF\) if \(\{R\cap Q:R\in\cF\}=2^Q\). The VC dimension \(\VCdim(\cF)\) is the largest size of a shattered set. \begin{lemma}\label{lem:incidence} Suppose \(\cA_{\vecH}(V(H))\) shatters \(Q\subseteq S(\vecH)\). Let \(\cL\) be a nonempty family of distinct nonempty subsets of \(Q\) such that every two members intersect. Suppose every \(q\in Q\) belongs to at most \(\Delta\) members of \(\cL\). Then \[ \fdtw(H)\ge\frac{|\cL|}{\Delta}. \tag{3.2}\label{eq:incidence} \] \end{lemma} \begin{proof} For each \(L\in\cL\), shattering supplies a vertex \(v_L\) such that \(\sigma_{\vecH}(v_L)\cap Q=L\). Distinct traces require distinct vertices. Since \(L\ne\varnothing\), every \(v_L\) belongs to the region \(U\) in Lemma~\ref{lem:reorient}. In the resulting orientation \(\vecH_Q\), \[ \sigma_{\vecH_Q}(v_L)=L. \tag{3.3}\label{eq:exact-L} \] Let \(K=\{v_L:L\in\cL\}\). For distinct \(L,L'\), choose \(q\in L\cap L'\). The reachability edge \(R_{\vecH_Q}(q)\) contains \(v_L,v_{L'}\), so \(K\) is a clique in the primal graph of \(\cR(\vecH_Q)\). Lemma~\ref{lem:clique} forces \(K\) into a bag of every tree decomposition. Let \((\gamma_s)_{s\in S(\vecH_Q)}\) be a fractional reachability-edge cover of such a bag. By \eqref{eq:exact-L}, the constraint at \(v_L\) is \[ \sum_{q\in L}\gamma_q\ge1. \] Summing over \(L\in\cL\) gives \[ |\cL| \le\sum_{L\in\cL}\sum_{q\in L}\gamma_q =\sum_{q\in Q}\deg_{\cL}(q)\gamma_q \le\Delta\sum_{s\in S(\vecH_Q)}\gamma_s. \] Every decomposition therefore has a bag of fractional cover cost at least \(|\cL|/\Delta\). Hence \[ \fhtw(\cR(\vecH_Q))\ge\frac{|\cL|}{\Delta}. \] Maximizing over orientations proves \eqref{eq:incidence}. \end{proof} \begin{example}[the Fano-plane witness]\label{ex:fano} Suppose a profile family shatters seven sources. Identify them with the points of the projective plane over \(\mathbb F_2\). Its seven lines are three-element sets; every two lines intersect, and every point lies on three lines. Lemma~\ref{lem:incidence}, after reorientation, produces seven exact-profile vertices forming a primal clique and gives \[ \fdtw(H)\ge\frac73. \] Thus even though the profiles were initially only specified by their traces on seven sources, the all-orientations maximum converts their finite geometry into an unavoidable fractional-width obstruction. \end{example} \subsection{Bounding profile VC dimension} \begin{theorem}\label{thm:vc} Let \(H\) be nonempty and put \(F=\fdtw(H)\). For every \(\vecH\in\Acyc(H)\), \[ \VCdim\bigl(\cA_{\vecH}(V(H))\bigr)<5F^2. \tag{3.4}\label{eq:vc-bound} \] \end{theorem} \begin{proof} First \(F\ge1\). Every acyclic orientation of a nonempty graph has a source, hence a nonempty reachability edge. Every decomposition has a bag containing that edge, and a fractional cover of a nonempty bag has cost at least one. Fix \(\vecH\), and write \[ d=\VCdim\bigl(\cA_{\vecH}(V(H))\bigr). \] If \(d\le2\), then \(d<5\le5F^2\). If \(3\le d\le6\), take three points \(q_1,q_2,q_3\) of a shattered source set and use \[ \cL=\{\{q_1,q_2\},\{q_1,q_3\},\{q_2,q_3\}\}. \] The sets are pairwise intersecting and every point has incidence two. Lemma~\ref{lem:incidence} gives \(F\ge3/2\), so \[ d\le6<\frac{45}{4}\le5F^2. \] It remains to consider \(d\ge7\). For \(t\ge1\), put \(N_t=t^2+t+1\), and choose the largest power of two \(t\) such that \(N_t\le d\). This exists because \(N_2=7\). By maximality, \[ dt. \] Since \(t\ge2\), one has \(2t\le t^2\), and therefore \[ d\le4t^2+2t\le5t^2<5F^2. \] This proves \eqref{eq:vc-bound} in every case. \end{proof} \section{Weighted epsilon-net rounding} We now prove the required set-cover rounding estimate. The constants are kept explicit because they propagate directly to the main theorem. \begin{lemma}[pullbacks and random equipartitions]\label{lem:pullback} Let \(\cF\) have VC dimension at most \(d\) on a finite ground set, and let \(z_1,\ldots,z_n\) be ground elements, with repetitions allowed. Then the family on labeled positions \[ \cF_z=\{\{i\in[n]:z_i\in R\}:R\in\cF\} \] has VC dimension at most \(d\). Moreover, if \(A\subseteq[2s]\) has size \(k\), and \(I\) is a uniformly random \(s\)-element subset of \([2s]\), then \[ \Pr(I\cap A=\varnothing) =\frac{\binom{2s-k}{s}}{\binom{2s}{s}} \le2^{-k} \tag{4.1}\label{eq:partition} \] when \(k\le s\), and the probability is zero when \(k>s\). \end{lemma} \begin{proof} If a position set \(J\) were shattered by \(\cF_z\), two positions in \(J\) could not carry the same ground element: every trace would contain either both or neither. Thus \(i\mapsto z_i\) is injective on \(J\), and shattering \(J\) implies that \(\{z_i:i\in J\}\) is shattered by \(\cF\). Hence \(|J|\le d\). For the probability statement, \(I\) avoids \(A\) exactly when all of its elements are chosen among the \(2s-k\) positions outside \(A\). If \(k\le s\), \[ \frac{\binom{2s-k}{s}}{\binom{2s}{s}} =\prod_{j=0}^{k-1}\frac{s-j}{2s-j} \le\prod_{j=0}^{k-1}\frac12=2^{-k}. \] If \(k>s\), fewer than \(s\) positions remain outside \(A\), so the probability is zero. \end{proof} \begin{theorem}[fractional transversals in bounded VC dimension] \label{thm:epsilon-net} Let \(\cF\) be a nonempty family of nonempty subsets of a finite ground set. Put \[ d=\VCdim(\cF),\qquad C=\tau^*(\cF). \] If \(d=0\), then \(\tau(\cF)=1\). If \(d\ge1\), then \[ \tau(\cF)\le32dC\ln(16C). \tag{4.2}\label{eq:epsilon-net} \] \end{theorem} \begin{proof} Suppose first that \(d=0\). Choose \(R\in\cF\) and \(a\in R\). If some member of \(\cF\) omitted \(a\), the traces on \(\{a\}\) would contain both \(\{a\}\) and \(\varnothing\), shattering that singleton. Thus every range contains \(a\), and \(\tau(\cF)=1\). Now assume \(d\ge1\). We first establish a weighted epsilon-net estimate. Let \(\mu\) be a probability distribution on the ground set, let \(0<\varepsilon\le1\), and put \[ s=\left\lceil 16d\varepsilon^{-1}\ln(16/\varepsilon) \right\rceil. \tag{4.3}\label{eq:sample-size} \] Take two independent ordered samples \(S,T\), each consisting of \(s\) independent draws from \(\mu\). Let \(E\) be the event that \(S\) misses a range \(R\) with \(\mu(R)\ge\varepsilon\). For each realization in \(E\), select one such \(R\). The number of positions of \(T\) falling in \(R\) has binomial mean at least \(\varepsilon s\). More explicitly, if \(X\) is binomial with parameters \(s,p\), and \(m=sp\), then Markov's inequality gives \[ \Pr(X2\), the function \(2L-\ln(6L)\) has positive derivative and its value at \(L=2\) is \(4-\ln12>0\). Thus \(\ln(6L)\le2L\), which implies \[ (2es/d)^d\le\exp(3dL). \] Also \(\varepsilon s\ge16dL\), so \[ 2^{-\varepsilon s/2}\le\exp(-8(\ln2)dL). \] The right side of \eqref{eq:failure} is therefore at most \[ 2\exp\bigl(-(8\ln2-3)dL\bigr)<1. \] Indeed, \(\ln2>1/2\), \(d\ge1\), and \(L\ge\ln16\) bound this expression by \(2e^{-L}\le1/8\). Some realization of \(S\) meets every range of measure at least \(\varepsilon\). Removing repeated points gives such an epsilon-net of size at most \(s\). Return to fractional transversals. Let \((x_a)\) be an optimal fractional transversal. Since \(\cF\) is nonempty and its members are nonempty, \[ C=\sum_a x_a\ge1. \] Define \(\mu(a)=x_a/C\). Every \(R\in\cF\) satisfies \[ \mu(R)=\frac1C\sum_{a\in R}x_a\ge\frac1C. \] Apply the weighted epsilon-net estimate with \(\varepsilon=1/C\). It gives a transversal of size at most \[ \left\lceil16dC\ln(16C)\right\rceil \le32dC\ln(16C), \] where the last inequality follows because \(16dC\ln(16C)>1\). This proves \eqref{eq:epsilon-net}. \end{proof} \section{The integral-width bound} We first note why bagwise rounding uses precisely the width notion in the source. A hypergraph tree decomposition is equivalent to a tree decomposition of its primal graph. One direction is immediate. In the other direction, the vertices of a hyperedge form a primal clique, so Lemma~\ref{lem:clique} places the whole hyperedge in a bag. For a fixed bag, a minimum integral guard family is exactly an edge cover of that bag, and a minimum fractional guard is exactly a fractional edge cover. Generalized hypertreewidth imposes no condition coupling guards at different nodes. It is therefore valid to retain one tree and all its bags while rounding their covers independently. \begin{theorem}\label{thm:main} For every nonempty finite graph \(H\), if \(F=\fdtw(H)\), then \[ \dtw(H)\le160F^3\ln(16F). \tag{5.1}\label{eq:main} \] For the null graph, \(\dtw(H)=\fdtw(H)=0\). \end{theorem} \begin{proof} Assume \(H\) is nonempty, so \(F\ge1\). Fix an arbitrary \(\vecH\in\Acyc(H)\), and let \(\eta>0\). Choose a tree decomposition \((T,(B_t))\) of \(\cR(\vecH)\) having fractional width at most \[ \fhtw(\cR(\vecH))+\eta\le F+\eta. \tag{5.2}\label{eq:eta} \] Fix a nonempty bag \(B_t\) and put \[ C_t=\rho^*_{\cR(\vecH)}(B_t). \] Then \(1\le C_t\le F+\eta\). By Lemma~\ref{lem:duality}, \[ C_t=\tau^*(\cA_{\vecH}(B_t)). \] Let \(d_t=\VCdim(\cA_{\vecH}(B_t))\). A subfamily cannot have larger VC dimension than the full profile family, so Theorem~\ref{thm:vc} gives \[ d_t<5F^2. \tag{5.3}\label{eq:bag-vc} \] If \(d_t=0\), Theorem~\ref{thm:epsilon-net} gives integral cover number one. If \(d_t\ge1\), the same theorem and Lemma~\ref{lem:duality} give \begin{align*} \rho_{\cR(\vecH)}(B_t) &=\tau(\cA_{\vecH}(B_t))\\ &\le32d_tC_t\ln(16C_t)\\ &\le160F^2(F+\eta)\ln\!\bigl(16(F+\eta)\bigr). \tag{5.4}\label{eq:bag-round} \end{align*} The final expression exceeds one, so it also covers the case \(d_t=0\); empty bags have cover number zero. Thus the same tree and the same bags form an integral generalized hypertree decomposition of width at most the last expression in \eqref{eq:bag-round}. Therefore \[ \htw(\cR(\vecH)) \le160F^2(F+\eta)\ln\!\bigl(16(F+\eta)\bigr). \] Letting \(\eta\) tend to zero gives \[ \htw(\cR(\vecH))\le160F^3\ln(16F). \] Since \(\vecH\) was arbitrary, maximizing over all acyclic orientations proves \eqref{eq:main}. \end{proof} \begin{corollary}[boundedness equivalence]\label{cor:equivalence} For every finite graph \(H\), \[ \fdtw(H)\le\dtw(H). \] If \(H\) is nonempty, then \[ \dtw(H)\le 160\,\fdtw(H)^3\ln\!\bigl(16\fdtw(H)\bigr). \] Consequently, define \[ g(0)=0,\qquad g(k)=\left\lceil160k^3\ln(16k)\right\rceil \quad(k\ge1). \] Then \[ \dtw(H)\le g(\lceil\fdtw(H)\rceil) \] for every finite graph \(H\), and Question~\ref{question:source} has an affirmative answer. \end{corollary} \begin{proof} Every integral edge cover is a fractional edge cover, so \(\fhtw(\mathcal H)\le\htw(\mathcal H)\) for every hypergraph \(\mathcal H\). Taking maxima in \eqref{eq:dag-widths} gives the first inequality. The second is Theorem~\ref{thm:main}. The function \(x\mapsto x^3\ln(16x)\) is increasing for \(x\ge1\), which gives the integer-valued bound using \(g\). Applying the two pointwise inequalities uniformly over a graph class proves both directions of the boundedness equivalence. \end{proof} \section{Concluding remarks} The exponent and constant in the bound leave room for improvement. One question is how tightly fractional DAG treewidth controls the VC dimension of source profiles; another is whether the resulting width comparison can avoid some of the loss from general-purpose rounding. Algorithmic set-cover methods such as \cite{BG} address the local rounding step, but constructing suitable decompositions and handling the maximum over orientations require additional work. An optimal decomposition algorithm does not follow from the boundedness theorem. \begin{thebibliography}{10} \bibitem{BLR} M.~Bressan, M.~Lanzinger, and M.~Roth, \emph{The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree}, STOC 2023, pp.~542--552. \href{https://doi.org/10.1145/3564246.3585204}{Conference version}. Full version: \href{https://arxiv.org/abs/2211.01905v1}{arXiv:2211.01905v1}, 2022. \bibitem{Bressan} M.~Bressan, \emph{Faster Algorithms for Counting Subgraphs in Sparse Graphs}, Algorithmica \textbf{83} (2021), 2578--2605. \href{https://doi.org/10.1007/s00453-021-00811-0}{doi:10.1007/s00453-021-00811-0}. Full version: \href{https://arxiv.org/abs/1805.02089v5}{arXiv:1805.02089v5}. \bibitem{GM} M.~Grohe and D.~Marx, \emph{Constraint Solving via Fractional Edge Covers}, ACM Transactions on Algorithms \textbf{11}(1) (2014), Article~4. \href{https://doi.org/10.1145/2636918}{doi:10.1145/2636918}. \href{https://arxiv.org/abs/1711.04506}{arXiv:1711.04506}. \bibitem{GLPR} G.~Gottlob, M.~Lanzinger, R.~Pichler, and I.~Razgon, \emph{Complexity Analysis of Generalized and Fractional Hypertree Decompositions}, Journal of the ACM (2021). \href{https://doi.org/10.1145/3457374}{doi:10.1145/3457374}. Full version: \href{https://arxiv.org/abs/2002.05239v2}{arXiv:2002.05239v2}, 2020. \bibitem{HW} D.~Haussler and E.~Welzl, \emph{Epsilon-Nets and Simplex Range Queries}, Proceedings of the Second Annual Symposium on Computational Geometry (SoCG 1986), pp.~61--71. \href{https://doi.org/10.1145/10515.10522}{Conference version}. \bibitem{BG} H.~Br\"onnimann and M.~T.~Goodrich, \emph{Almost Optimal Set Covers in Finite VC-Dimension}, Discrete \& Computational Geometry \textbf{14} (1995), 463--479. \href{https://doi.org/10.1007/BF02570718}{doi:10.1007/BF02570718}. \bibitem{Sauer} N.~Sauer, \emph{On the Density of Families of Sets}, Journal of Combinatorial Theory, Series~A \textbf{13}(1) (1972), 145--147. \href{https://doi.org/10.1016/0097-3165(72)90019-2}{doi:10.1016/0097-3165(72)90019-2}. \bibitem{Shelah} S.~Shelah, \emph{A Combinatorial Problem; Stability and Order for Models and Theories in Infinitary Languages}, Pacific Journal of Mathematics \textbf{41}(1) (1972), 247--261. \href{https://doi.org/10.2140/pjm.1972.41.247}{doi:10.2140/pjm.1972.41.247}. \bibitem{KKP} B.~Komarath, A.~Kumar, and A.~Pareek, \emph{Counting Patterns in Degenerate Graphs in Constant Space}, \href{https://arxiv.org/abs/2511.04258v2}{arXiv:2511.04258v2}, 30 June 2026. \bibitem{PS} D.~Paul-Pena and C.~Seshadhri, \emph{Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs}, ICALP 2025, LIPIcs \textbf{334}, Article~124, pp.~124:1--124:18. \href{https://doi.org/10.4230/LIPIcs.ICALP.2025.124}{Conference version}. \end{thebibliography} \end{document}