LFCS seminar: Georg Gottlob: General and Fractional Hypertree Decompositions: Hard and Easy Cases
What 


When 
Jun 28, 2018 from 10:30 AM to 11:30 AM 
Where  7 George Square, room F.21 
Add event to calendar 
vCal iCal 
Hypertree decompositions, as well as the more powerful generalized
hypertree decompositions (GHDs), and the yet more general fractional
hypertree decompositions (FHD) are hypergraph decomposition methods for
answering conjunctive queries and for the solution of constraint
satisfaction problems. Every hypergraph H has a width relative to each of
these decomposition methods: its hypertree width hw(H), its generalized
hypertree width ghw(H), and its fractional hypertree width fhw(H),
respectively. It is known that hw(H) <= k can be checked in polynomial
time for fixed k, while checking ghw(H) <= k is NPcomplete for any k
greater than or equal to 3. The complexity of checking fhw(H) <= k for a
fixed k has been open for more than a decade. We settle this open problem
by showing that checking fhw(H) <= k is NPcomplete, even for k=2. The
same construction allows us to prove also the NPcompleteness of checking
ghw(H) <= k for k=2. After proving these hardness results, we identify
meaningful restrictions, for which checking for bounded ghw or fhw becomes
tractable. In particular we look at bounded edge (multi)intersection,
bounded degree, and bounded VC dimension. Joint work with Wolfgang Fischl
and Reinhard Pichler.