Georg Gottlob
University of Oxford (UK)

General and Fractional Hypertree Decompositions: Hard and Easy Cases

Hypertree decompositions, the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. 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, 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 approximability results for fhw. We consider classes of hypergraphs whose fhw is bounded by a constant k and which also enjoy the BIP or MIP, or bounded VC-dimension. For each hypergraph in such a class, we are able to compute an FHD of width O(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.  Joint work with Wolfgang Fischl and Reingard Pichler.

Biography

Georg Gottlob is a Professor of  Informatics at Oxford University, a Fellow of St John's College, Oxford,  and an Adjunct Professor at TU Wien. His interests include AI, knowledge representation, logic and complexity, web data extraction, database theory, graphdecomposition techniques.  Gottlob is an ACM Fellow, an ECCAI Fellow, a Fellow of the Royal Society,  and a member of the Austrian Academy of Sciences, the German National Academy of Sciences, and the Academia Europaea. He chaired the Program Committees of IJCAI 2003 and ACM PODS 2000, was the Editor in Chief of the Journal Artificial Intelligence Communications, and is currently a member of the editorial boards of journals, such as JACM and the Journal of Computer and System Sciences.   Gottlob was awarded an ERC Advanced Investigator's Grant for the project "DIADEM: Domain-centric Intelligent Automated Data Extraction Methodology" (see also http://diadem.cs.ox.ac.uk/)




Important dates

Abstract submission
   February 17, 2017
   February 27, 2017
Paper submission:
   February 24, 2017
   March 5, 2017
Notification of acceptance:
   April 7, 2017
Camera-ready version:
   April 21, 2017
Conference:
   July 18-19, 2017
News
[04.07.17] Proceedings available here
[13.04.17]
Accepted papers announced
[16.02.17]
Paper submission deadline extended to March 5
[21.12.16] Georg Gottlob confirmed as invited speaker
[07.11.16]
CFP available in text, and PDF
[27.10.16] Website on-line
[21.09.16] JLAMP special issue confirmed
http://www.springer.com/lncs
http://www.ifip.org
http://www.eatcs.org http://easst.aulp.co.uk/