Fomin, Fedor V. ;
Golovach, Petr A. ;
Thilikos, Dimitrios M.
Approximating Acyclicity Parameters of Sparse Hypergraphs
Abstract
The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx in SODA'06, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. Computing each of these width parameters is known to be an NPhard problem. Moreover, the (generalized) hypertree width of an nvertex hypergraph cannot be approximated within a logarithmic factor unless P=NP. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph is constantfactor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apexminorfree graph class (the family of apexminorfree graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some Hminorfree graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of Hminorfree graphs.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2009:1803,
author = {Fedor V. Fomin and Petr A. Golovach and Dimitrios M. Thilikos},
title = {{Approximating Acyclicity Parameters of Sparse Hypergraphs}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {445456},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897095},
ISSN = {18688969},
year = {2009},
volume = {3},
editor = {Susanne Albers and JeanYves Marion},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1803},
URN = {urn:nbn:de:0030drops18034},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1803},
annote = {Keywords: Graph, Hypergraph, Hypertree width, Treewidth}
}
Keywords: 

Graph, Hypergraph, Hypertree width, Treewidth 
Seminar: 

26th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2009 
Date of publication: 

2009 