The Library
Solving d-SAT via backdoors to small Treewidth
Tools
Fomin, Fedor V., Lokshtanov, Daniel, Misra, Neeldhara, Ramanujan, Maadapuzhi Sridharan and Saurabh, Saket (2015) Solving d-SAT via backdoors to small Treewidth. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, San Diego, USA, 4–6 Jan 2015. Published in: Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 630-641. ISBN 9781611973747. doi:10.1137/1.9781611973730.43
|
PDF
WRAP-solving-d-SAT-via-backdoors-treewidth-Ramanujan-2015.pdf - Published Version - Requires a PDF viewer. Download (737Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611973730.43
Abstract
A backdoor set of a CNF formula is a set of variables such that fixing the truth values of the variables from this set moves the formula into a polynomial-time decidable class. In this work we obtain several algorithmic results for solving d-SAT, by exploiting backdoors to d-CNF formulas whose incidence graphs have small treewidth.
For a CNF formula F and integer t, a strong backdoor set to treewidth t is a set of variables such that each possible partial assignment τ to this set reduces F to a formula whose incidence graph is of treewidth at most t. A weak backdoor set to treewidth t is a set of variables such that there is a partial assignment to this set that reduces φ to a satisfiable formula of treewidth at most t. Our main contribution is an algorithm that, given a d-CNF formula F and an integer k, in time 2^{O(k)}|F|,
• either finds a satisfying assignment of F, or
• reports correctly that F is not satisfiable, or
• concludes correctly that F has no weak or strong backdoor set to treewidth t of size at most k.
As a consequence of the above, we show that d-SAT parameterized by the size of a smallest weak/strong backdoor set to formulas of treewidth t, is fixed-parameter tractable.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Computer science -- Congresses | ||||||
Journal or Publication Title: | Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
Publisher: | SIAM | ||||||
ISBN: | 9781611973747 | ||||||
Official Date: | 2015 | ||||||
Dates: |
|
||||||
Page Range: | pp. 630-641 | ||||||
DOI: | 10.1137/1.9781611973730.43 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 19 January 2018 | ||||||
Date of first compliant Open Access: | 22 January 2018 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 | ||||||
Type of Event: | Conference | ||||||
Location of Event: | San Diego, USA | ||||||
Date(s) of Event: | 4–6 Jan 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year