2024/09/30 by Viktoriia Korchemna, Korchemna, Viktoriia, Daniel Lokshtanov +7 · 1 citation
Computer Science · #Metaheuristic Optimization Algorithms Research #Advanced Data Compression Techniques #Digital Filter Design and Implementation
paper · pdf · doi:10.48550/arxiv.2409.20172
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 ω, runs in polynomial time and produces a tree decomposition of H of fractional hypertree width O(ωlog n log ω). As an immediate corollary this yields polynomial time O(log2 n log ω)-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 ω is considered a constant. For hypergraphs with the bounded intersection property we get better bounds, comparable with that recent algorithm of Lanzinger and Razgon [STACS 2024]. The second algorithm runs in time nωmO(1) and produces a tree decomposition of H of fractional hypertree width O(ωlog2 ω). This significantly improves over the (n+m)O(ω3) time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hypertree width O(ω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 \cal F of cliques in G, and positive rational f, either there exists a sub-family of O(f ⋅ log2 n) cliques in \cal F whose union separates A from B, or there exist f ⋅ log |\cal F| paths from A to B such that no clique in \cal F intersects more than log |\cal F| paths.