Efficient Approximation of Fractional Hypertree Width
Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan, Jie Xue · 2024
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.