General and Fractional Hypertree Decompositions: Hard and Easy Cases (Invited Talk)

摘要

Hypertree decompositions [5, 4], the more powerful generalized hypertree decompositions (GHDs) [5, 4], and the yet more general fractional hypertree decompositions (FHDs) [8, 9] are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. For a survey on these decompositions, see [3], for exact hypertree decomposition algorithms [7], and for heuristic decomposition methods, see [1]. Each hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw{H), and its fractional hypertree width fhw{H), respectively. While hw{H) ≤ k can be checked in polynomial time, the complexity of checking whether fhw(H) ≤ k holds for a fixed constant k was unknown. We settle this problem by proving that checking whether fhw(H) ≤ k is NP-complete, even for k = 2 and by same construction also the problem deciding whether ghw(H) ≤ k is NP-complete for k ≥ 2. Hardness was previously known for k ≥ 3 [6], whilst the case k = 2 has remained open since 2001. Given these hardness results, we investigate meaningful restrictions, for which checking for bounded ghw is easy. We study classes of hypergraphs that enjoy the bounded edge-intersection property (BIP) and the more general bounded multi-edge intersection property (BMIP). For such classes, for each constant k, checking whether ghw{H) ≤ k, and if so, computing a GHD of width k of H is tractable and actually FPT. Finally we derive some approx-imability results for fhw. We consider classes of hypergraphs whose fhw is bounded by a constant k and which also enjoy the BIP or M1P, or bounded VC-dimension. For each hypergraph in such a class, we are able to compute an FHD of width 0(k log k) efficiently. A different restriction on classes of hypergraphs gives a linear approximation in PTIME. Hypergraphs of bounded rank are a simple example of such a class. A full paper [2] with these and further results is available online via the link https://arxiv.org/abs/1611.01090.