Saket Saurabh

Efficient Approximation of Fractional Hypertree Width

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 …