Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorThilikos, Dimitrios
dc.date.accessioned2016-05-30T10:55:00Z
dc.date.available2016-05-30T10:55:00Z
dc.date.issued2009
dc.PublishedLeibniz International Proceedings in Informatics 2009, 3:445-456eng
dc.identifier.urihttps://hdl.handle.net/1956/12036
dc.description.abstractThe 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 NP-hard problem. Moreover, the (generalized) hypertree width of an n-vertex 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 constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free 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 H-minor-free graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of H-minor-free graphs.en_US
dc.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-ND 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/eng
dc.subjectGrapheng
dc.subjectHypergrapheng
dc.subjectHypertree widtheng
dc.subjectTreewidtheng
dc.titleApproximating Acyclicity Parameters of Sparse Hypergraphsen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-04-07T06:45:29Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright F. V. Fomin, P. A. Golovach, and D. M. Thilikosen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.stacs.2009.1803
dc.identifier.cristin352420
dc.subject.nsiVDP::Matematikk og naturvitenskap: 400::Matematikk: 410
dc.subject.nsiVDP::Mathematics and natural scienses: 400::Mathematics: 410
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY-ND 3.0
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY-ND 3.0