UC Santa Barbara

A (hyper)tree decomposition of a (hyper)graph is a way of grouping vertices into subsets called bags and arranging them in a tree-like structure. The quality or usefulness of such a decomposition depends on certain desirable properties or measure (width) of the bags. This thesis deals with computing (hyper)tree decompositions with large bags in theory and practice, and using them to design algorithms for fundamental problems.In the first part of the thesis, we design two algorithms for computing unbreakable decompositions – tree decompositions with unbreakable bags and small bag intersections. A bag is said to be (q, k)-(edge)-unbreakable if no (edge)-cut of size at most k in the graph can break the bag into two parts, both having at least q vertices. Given a graph G, and an integer k, our first algorithm computes in polynomial time an unbreakable decomposition of G with (poly(k), k)-edge-unbreakable bags and bag intersections of size 𝒪(k). The second algorithm, takes an unbreakable decomposition with (𝒪(k), k)-unbreakable bags and bag intersections of size 𝒪(k), and again in polynomial time, converts it into one having similar unbreakability and intersection guarantees but with logarithmic depth.In the second part of the thesis, we resolve the parameterized approximability of the classic Minimum k-Cut problem with respect to k. We design a parameterized approximation algorithm that for every ε > 0, obtains a (1 + ε)-approximate solution in time (k/ε)𝒪(k)n𝒪(1). This uses our first algorithm for computing unbreakable decompositions.Next we show that the technique introduced by [Lampis, ICALP ’18] for obtaining parameterized approximation algorithms for problems on bounded tree-width or clique-width graphs can be exploited even on general graphs using logarithmic depth unbreak- able decompositions. As a proof of concept for this technique, we design approximation algorithms for a fair version of the Minimum Bisection problem, which we introduce.Fractional hypertree width and generalized hypertree width are two commonly used width measures for hypertree decompositions that measure the bags in terms of their fractional edge covers and edge covers respectively. In the last part of the thesis, we first design two new algorithms for approximating the fractional hypertree width ω of an input hypergraph H on n vertices and m edges. These directly imply approximations for generalized hypertree width. One algorithm is the first polynomial time approximation algorithm for computing fractional hypertree width, it has a ratio of 𝒪(log n log ω). For hypergraphs with each pair of hyperedges having at most η vertices in common, the algorithm is a 𝒪(ηω log ω)-approximation. The second algorithm is a nω m𝒪(1) time 𝒪(log2 ω)-approximation. This significantly improves over the (n + m)𝒪(ω3) time 𝒪(ω2)- approximation algorithm of [Marx, ACM TALG 2010]. A key insight behind both algorithms is a new variant of the classic Menger’s Theorem for clique separators in graphs.Finally, we present Ralph (Randomized Approximation using Linear Programming for Hypertree-Decompositions), a fast algorithm to compute low width fractional and generalized hypertree decompositions for input hypergraphs, as well as lower bounds for these widths. Our approach combines our polynomial time approximation algorithm with practical heuristic improvements utilizing (mixed-integer) linear programs. Through empirical evaluation on the nearly 3700 instances of HyperBench, a well established benchmark suite for hypertree decompositions, we find near optimal decompositions for all previously solved instances and low width decompositions for all 500 previously unsolved instances.