Using Decomposition-Parameters for QBF : Mind the Prefix! / Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian.

2016. 964-970 Paper presented at Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, United States.

Research output: Contribution to conferencePaper

Published

Abstract

Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF.
Original languageEnglish
Pages964-970
Number of pages7
DOIs
Publication statusPublished - 21 Feb 2016
EventThirtieth AAAI Conference on Artificial Intelligence - Phoenix, United States
Duration: 12 Feb 201617 Feb 2016
https://www.aaai.org/Conferences/AAAI/aaai16.php

Conference

ConferenceThirtieth AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI 2016
CountryUnited States
CityPhoenix
Period12/02/1617/02/16
Internet address
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 34924607