Efficient Approximation of Fractional Hypertree Width

Abstract

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega\log n\log\omega)$, i.e., it is an $\mathcal{O}(\log n\log\omega)$-approximation algorithm. As an immediate corollary this yields poly-nomial time $\mathcal{O}(\log^{2}n\log\omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs where every pair of hyperedges have at most $\eta$ vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width $\mathcal{O}(\eta\omega^{2}\log\omega)$ and generalized hypertree width $\mathcal{O}(\eta\omega^{2}\log\omega(\log\eta+\text{log}\omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width ${\mathcal{O}}(\omega^{2}(\omega+\eta))$, but uses time (at least) exponential in $\eta$ and $\omega$. The second algorithm runs in time $n^{\omega}m^{\mathcal{O}(1)}$ and pro-duces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega{\mathrm{l}}\text{og}^{2}\omega)$. This significantly improves over the $(n+m)^{\mathcal{O}(\omega^{3})}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width $\mathcal{O}(\omega^{3})$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family $\mathcal{F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $\mathcal{O}(f \cdot {\mathrm{l}}\text{og}^{2}n)$ cliques in $\mathcal{F}$ whose union separates $A$ from $B$, or there exist $f\cdot\log\vert \mathcal{F}\vert$ paths from $A$ to $B$ such that no clique in $\mathcal{F}$ intersects more than $\log\vert \mathcal{F}\vert$ paths.