FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs

Abstract

Generalised hypertree width (ghw) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing ghw of a hypergraph is notoriously hard. The decision version of the problem, checking whether ghw(H) ≤ k, is paraNP-hard when parameterised by k. Furthermore, approximation of ghw is at least as hard as approximation of Set-Cover, which is known to not admit any <ani:sans-serif>FPT</ani:sans-serif> approximation algorithms (assuming W[1] ≠ <ani:sans-serif>FPT</ani:sans-serif>). Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs — such as bounds on the size of edge intersections — that permit XP algorithms for ghw. Yet, even under these restrictions the problem has so far evaded any kind of <ani:sans-serif>FPT</ani:sans-serif> algorithm. In this article, we make the first step towards <ani:sans-serif>FPT</ani:sans-serif> algorithms for ghw by showing that the parameter can be approximated in <ani:sans-serif>FPT</ani:sans-serif> time for graphs of bounded edge intersection size. In concrete terms we show that there exists an <ani:sans-serif>FPT</ani:sans-serif> algorithm, parameterised by k and d, that for input hypergraph H with maximal cardinality of edge intersections d and integer k either outputs a tree decomposition with ghw(H) ≤ 4k(k+d+1)(2k-1), or rejects, in which case it is guaranteed that ghw(H) > k. Thus, in the special case of hypergraphs of bounded edge intersection, we obtain an <ani:sans-serif>FPT</ani:sans-serif> O(k³)-approximation algorithm for ghw.