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
|
|
|
|
|
|
|
|
|
|
