Back to search

University of Waterloo

An Analysis of the Effect of Community Structure on SAT Solver Performance

Abstract

dc:description.abstract

Despite enormous improvements in Boolean SATisfiability solver performance over the last decade, it is still unclear why specific input formula are slow to solve, when other similarly specified formula execute more quickly. This work explores the relationship between the community structure of a SAT formula and its execution time on several state-of-the-art solvers. We explore the analysis of this data from a number of directions; first, we explore the relationship between the well known clause-variable ratio result, and com- munity structure in randomly generated instances. Second, we perform a standard linear regression on data obtained from the 2013 SAT competition. Third, we present a visualisation tool and data repository for viewing the structure of a SAT formula. Fourth, we explore the effect of hardware con- straints on the solution time of instances across various machines. Finally, we explore survival analysis, a technique that is new to the field of Boolean SATisfiability. By collating the results from each of these experiments, we have determined that the community structure is critical in determining the solution time of a SAT formula, more important than the clause-variable ratio of the formula. While this work is not a complete explanation of the varying solution time of SAT formulae, it has provided us with significant insight for further research to answer the question: why different similarly specified formula have such different solution times?

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Newsham, Zackary

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9110

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Newsham, Zackary. An Analysis of the Effect of Community Structure on SAT Solver Performance. University of Waterloo, 2015. http://hdl.handle.net/10012/9110