• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

QBF as an Alternative to Courcelle’s Theorem

Lampis, Michael; Mengel, Stefan; Mitsou, Valia (2018), QBF as an Alternative to Courcelle’s Theorem, in Olaf Beyersdorff; Christoph M. Wintersteiger, Theory and Applications of Satisfiability Testing – SAT 2018, 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9–12, 2018, Proceedings, Springer International Publishing : Berlin, p. 235-252. 10.1007/978-3-319-94144-8_15

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1805.08456v1
Date
2018
Conference title
21st International Conference on Theory and Applications of Satisfiability Testing – SAT 2018
Conference date
2018-07
Conference city
Oxford
Conference country
United Kingdom
Book title
Theory and Applications of Satisfiability Testing – SAT 2018, 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9–12, 2018, Proceedings
Book author
Olaf Beyersdorff; Christoph M. Wintersteiger
Publisher
Springer International Publishing
Published in
Berlin
ISBN
978-3-319-94143-1
Pages
235-252
Publication identifier
10.1007/978-3-319-94144-8_15
Metadata
Show full item record
Author(s)
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mengel, Stefan
Centre de Recherche en Informatique de Lens [CRIL]
Mitsou, Valia
Institut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
Abstract (EN)
We propose reductions to quantified Boolean formulas (QBF) as a new approach to showing fixed-parameter linear algorithms for problems parameterized by treewidth. We demonstrate the feasibility of this approach by giving new algorithms for several well-known problems from artificial intelligence that are in general complete for the second level of the polynomial hierarchy. By reduction from QBF we show that all resulting algorithms are essentially optimal in their dependence on the treewidth. Most of the problems that we consider were already known to be fixed-parameter linear by using Courcelle’s Theorem or dynamic programming, but we argue that our approach has clear advantages over these techniques: on the one hand, in contrast to Courcelle’s Theorem, we get concrete and tight guarantees for the runtime dependence on the treewidth. On the other hand, we avoid tedious dynamic programming and, after showing some normalization results for CNF-formulas, our upper bounds often boil down to a few lines.
Subjects / Keywords
quantified Boolean formulas

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Algorithms for Parity Games 
    Gajarsky, Jakub; Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Ordyniak, Sebastian (2015) Communication / Conférence
  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
  • Thumbnail
    Defective Coloring on Classes of Perfect Graphs 
    Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2017) Communication / Conférence
  • Thumbnail
    Scrabble is PSPACE-Complete 
    Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo