Title: Efficient counting with bounded treewidth using datalog
Language: English
Authors: Rümmele, Stefan
Qualification level: Diploma
Keywords: Abzählkomplexität; Parametrisierte Komplexität; Baumbreite; Datalog
Counting complexity; Parameterized complexity; Treewidth; Datalog
Advisor: Pichler, Reinhard
Assisting Advisor: Woltran, Stefan
Issue Date: 2008
Number of Pages: 76
Qualification level: Diploma
Bounded treewidth has proven to be a key concept in identifying tractable fragments of inherently intractable problems. An important result in this context is Courcelle's Theorem, stating that any property of finite structures definable in monadic second-order logic (MSO), becomes tractable if the treewidth of the structure is bounded by a constant. An extension of this result to counting problems was done by Arnborg et al. But both proofs did not yield an implementable algorithm.
Recently Gottlob et al.\ presented a new approach using monadic datalog to close this gap for decision problems. The goal of this work is to extend this method in order to handle counting problems as well. We show that the monadic datalog approach indeed is applicable for all MSO definable counting problems. Furthermore we propose concrete algorithms with fixed-parameter linear running time for the problems #SAT, #CIRCUMSCRIPTION and #HORN-ABDUCTION.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-22267
Library ID: AC05039694
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Efficient counting with bounded treewidth using datalog.pdf601.17 kBAdobe PDFThumbnail
Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.