Thursday, May 19, 2016

[DMANET] International Workshop on Graph Structure and Satisfiability Testing

Call for Presentations

International Workshop on Graph Structure and Satisfiability Testing

colocated with the 19th International Conference on Theory and Applications
Satisfiability Testing (SAT 2016).



A well-established way of describing the structure of SAT instances is to
consider different graphs or hypergraphs that encode the interaction of the
variables in CNF formulas. These graph structures have seen interest in the
last few years both from theory and practice of SAT solving. For example,
tractable classes of SAT and related problems are characterized by
restrictions of the underlying graph or hypergraph structure whereas lower
bounds in proof complexity and knowledge compilation often use graphs that
in a
certain well-defined sense lack this structure. On the more practical side,
has been shown that good performance of CDCL solvers on practical SAT
instances is related to the community structure of the underlying graphs.
Moreover, graphs play a crucial role in some successful variable choice
heuristics. Yet another connection between SAT and graph theory is the
increasing use of SAT solvers in combinatorial problems, for instance in

The goal of the International Workshop on Graph Structure and
Testing is to bring together researchers from different areas in which
there is
an interaction between graph structure and problems related to
satisfiability. The aim is to foster exchange between these areas by
different perspectives, results and current challenges.

The workshop will feature one 50-minute invited talk and several short
contributed talks highlighting different perspectives.


We solicit contributions in the form of 1-2-page extended abstracts
with all aspects of current research that relates graphs and SAT,
in a broad sense. Since there will be no proceedings, we explicitly solicit
the submission of talk abstracts describing already published work and work
progress which falls into the scope of our workshop.

The topics of interest include (but are not limited to) the following:

SAT algorithms based on graph structure
Model counting
Knowledge compilation
Proof complexity
Practical evaluation of graph based algorithms
Variable choice heuristics
Propagation algorithms
Analysis and visualization of the structure of practical instances
Applications of SAT-based techniques to combinatorial problems

Authors of accepted abstracts are expected to give a talk at the workshop.


Invited Speaker

Stefan Szeider (TU Wien)

Important Dates

May, 22th, 2016: Submission
June, 1st, 2016: Notification
July, 4th, 2016: Workshop

Program Committee

Gilles Audemard, CRIL, Université d'Artois
Simone Bova, TU Wien (organizer)
Massimo Lauria, Universitat Politecnica de Catalunya
Stefan Mengel, CNRS, CRIL (organizer)
Igor Razgon, Birkbeck, University of London

Additional information

* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.