All reports by Author Patrick Scharpfenecker:

__
TR16-024
| 22nd February 2016
__

Patrick Scharpfenecker, Jacobo Toran#### Solution-Graphs of Boolean Formulas and Isomorphism

__
TR15-101
| 15th June 2015
__

Patrick Scharpfenecker#### On the structure of Solution-Graphs for Boolean Formulas

Revisions: 2

__
TR15-100
| 16th June 2015
__

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran#### Succinct Encodings of Graph Isomorphism

Patrick Scharpfenecker, Jacobo Toran

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

Patrick Scharpfenecker

In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... more >>>

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>