A QSAT Benchmark Based on Vertex-Folkman Problems

The purpose of this project is to draw attention to a particular family of quantified Boolean formulas (QBFs) stemming from encodings of some vertex Folkman problems in extremal graph theory. We argue that this family of formulas is interesting for QSAT research because it is both conceptually simple and parametrized in a way that allows for a fine-grained diversity in the level of difficulty of its instances. Additionally, when coupled with symmetry breaking, the formulas in this family exhibit backbones (unique satisfying assignments) at the top-level existential variables. This benchmark is thus suitable for addressing questions regarding the connection between the existence of backbones and the hardness of QBFs.

Tags
Data and Resources
To access the resources you must log in

This item has no data

Identity

Description: The Identity category includes attributes that support the identification of the resource.

Field Value
PID https://www.doi.org/10.5281/zenodo.3548976
PID https://www.doi.org/10.5281/zenodo.3548977
URL https://figshare.com/articles/A_QSAT_Benchmark_Based_on_Vertex-Folkman_Problems/10566437
URL http://dx.doi.org/10.5281/zenodo.3548977
URL https://zenodo.org/record/3548977
URL http://dx.doi.org/10.5281/zenodo.3548976
URL https://figshare.com/articles/A_QSAT_Benchmark_Based_on_Vertex-Folkman_Problems/10566434
Access Modality

Description: The Access Modality category includes attributes that report the modality of exploitation of the resource.

Field Value
Access Right Open Source
Attribution

Description: Authorships and contributors

Field Value
Author Narváez, David, 0000-0003-3704-1060
Publishing

Description: Attributes about the publishing venue (e.g. journal) and deposit location (e.g. repository)

Field Value
Collected From Zenodo; Datacite; figshare
Hosted By Zenodo; figshare
Publication Date 2019-11-20
Publisher Zenodo
Additional Info
Field Value
Language UNKNOWN
Resource Type Software
system:type software
Management Info
Field Value
Source https://science-innovation-policy.openaire.eu/search/software?softwareId=dedup_wf_001::376aa171aae711bdd615cd02fcc8caaf
Author jsonws_user
Last Updated 17 December 2020, 19:15 (CET)
Created 17 December 2020, 19:15 (CET)