Change search
ReferencesLink to record
Permanent link

Direct link
Algorithmic Meta-Theorems for Restrictions of Treewidth
City University of New York.
2010 (English)In: ALGORITHMS-ESA 2010 / [ed] DeBerg, M; Meyer, U, Springer Berlin/Heidelberg, 2010, 549-560 p.Conference paper (Refereed)
Abstract [en]

Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees. We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number. We prove stronger algorithmic meta-theorems for these more restricted classes of graphs. More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2010. 549-560 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 6346
Keyword [en]
Algorithms, Computability and decidability, Graphic methods
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-58578DOI: 10.1007/978-3-642-15775-2_47ISI: 000286580200047ISBN: 978-3-642-15774-5OAI: diva2:473380
18th Annual European Symposium on Algorithms, ESA 2010; Liverpool; 6 September 2010 through 8 September 2010
QC 20120109Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2012-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lampis, Michael
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link