Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Georg Gottlob: General and Fractional Hypertree Decompositions: Hard and Easy Cases

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 NP-complete 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 NP-complete, even for k=2. The 
same construction allows us to prove also the NP-completeness 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.

Document Actions