Change search
ReferencesLink to record
Permanent link

Direct link
Parameterized Complexity of DPLL Search Procedures
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4003-3168
2013 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, Vol. 14, no 3, 20- p.Article in journal (Refereed) Published
Abstract [en]

We study the performance of DPLL algorithms on parameterized problems. In particular, we investigate how difficult it is to decide whether small solutions exist for satisfiability and other combinatorial problems. For this purpose we develop a Prover-Delayer game that models the running time of DPLL procedures and we establish an information-theoretic method to obtain lower bounds to the running time of parameterized DPLL procedures. We illustrate this technique by showing lower bounds to the parameterized pigeonhole principle and to the ordering principle. As our main application we study the DPLL procedure for the problem of deciding whether a graph has a small clique. We show that proving the absence of a k-clique requires n(Omega(k)) steps for a nontrivial distribution of graphs close to the critical threshold. For the restricted case of tree-like Parameterized Resolution, this result answers a question asked by Beyersdorff et al. [2012] of understanding the Resolution complexity of this family of formulas.

Place, publisher, year, edition, pages
2013. Vol. 14, no 3, 20- p.
Keyword [en]
Algorithms, Theory, Proof complexity, parameterized complexity, resolution, prover-delayer games
National Category
Computer Science
URN: urn:nbn:se:kth:diva-129463DOI: 10.1145/2499937.2499941ISI: 000323892900004ScopusID: 2-s2.0-84879381038OAI: diva2:653398

QC 20131004

Available from: 2013-10-04 Created: 2013-09-30 Last updated: 2013-10-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lauria, Massimo
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Computational Logic
Computer 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: 21 hits
ReferencesLink to record
Permanent link

Direct link