research
∙
06/17/2023
Co-Certificate Learning with SAT Modulo Symmetries
We present a new SAT-based method for generating all graphs up to isomor...
share
research
∙
10/13/2022
Threshold Treewidth and Hypertree Width
Treewidth and hypertree width have proven to be highly successful struct...
research
∙
06/30/2022
Are Hitting Formulas Hard for Resolution?
Hitting formulas, introduced by Iwama, are an unusual class of propositi...
research
∙
06/03/2022
Weighted Model Counting with Twin-Width
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and ...
research
∙
06/01/2022
Algorithmic Applications of Tree-Cut Width
The recently introduced graph parameter tree-cut width plays a similar r...
research
∙
02/16/2022
SAT Backdoors: Depth Beats Size
For several decades, much effort has been put into identifying classes o...
research
∙
10/12/2021
A SAT Approach to Twin-Width
The graph invariant twin-width was recently introduced by Bonnet, Kim, T...
research
∙
06/04/2021
Certified DQBF Solving by Definition Extraction
We propose a new decision procedure for dependency quantified Boolean fo...
research
∙
03/05/2021
Formalizing Graph Trail Properties in Isabelle/HOL
We describe a dataset expressing and proving properties of graph trails,...
research
∙
08/05/2020
A Time Leap Challenge for SAT Solving
We compare the impact of hardware advancement and algorithm advancement ...
research
∙
06/24/2020
Turbocharging Treewidth-Bounded Bayesian Network Structure Learning
We present a new approach for learning the structure of a treewidth-boun...
research
∙
11/29/2019
SAT-Encodings for Treecut Width and Treedepth
In this paper we propose, implement, and test the first practical decomp...
research
∙
11/04/2019
On Clustering Incomplete Data
We study fundamental clustering problems for incomplete data. In this se...
research
∙
07/29/2019
A Join-Based Hybrid Parameter for Constraint Satisfaction
We propose joinwidth, a new complexity parameter for the Constraint Sati...
research
∙
04/10/2018
Parameterized Algorithms for the Matrix Completion Problem
We consider two matrix completion problems, in which we are given a matr...
research
∙
09/18/2015
Backdoors into Heterogeneous Classes of SAT and CSP
In this paper we extend the classical notion of strong and weak backdoor...
research
∙
06/12/2014
Guarantees and Limits of Preprocessing in Constraint Satisfaction and Reasoning
We present a first theoretical analysis of the power of polynomial-time ...
research
∙
02/25/2014
The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
We study the computational complexity of problems that arise in abstract...
research
∙
02/04/2014
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
Bayesian network structure learning is the notoriously difficult problem...
research
∙
07/16/2013
Parameterized Complexity Results for Plan Reuse
Planning is a notoriously difficult computational problem of high worst-...
research
∙
04/22/2013
Backdoors to Abduction
Abductive reasoning (or Abduction, for short) is among the most fundamen...
research
∙
04/19/2013
Local Backbones
A backbone of a propositional CNF formula is a variable whose truth valu...
research
∙
01/08/2013
Backdoors to Normality for Disjunctive Logic Programs
Over the last two decades, propositional satisfiability (SAT) has become...
research
∙
11/02/2012
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
The propositional planning problem is a notoriously difficult computatio...
research
∙
08/13/2012
The Complexity of Planning Revisited - A Parameterized Analysis
The early classifications of the computational complexity of planning un...
research
∙
08/08/2012
On Finding Optimal Polytrees
Inferring probabilistic networks from data is a notoriously difficult ta...
research
∙
04/27/2012
Strong Backdoors to Bounded Treewidth SAT
There are various approaches to exploiting "hidden structure" in instanc...
research
∙
04/13/2012
Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough
Cardinality constraints or, more generally, weight constraints are well ...
research
∙
03/15/2012
Algorithms and Complexity Results for Exact Bayesian Structure Learning
Bayesian structure learning is the NP-hard problem of discovering a Baye...
research
∙
02/20/2012
Strong Backdoors to Nested Satisfiability
Knuth (1990) introduced the class of nested formulas and showed that the...
research
∙
10/28/2011
Backdoors to Satisfaction
A backdoor set is a set of variables of a propositional formula such tha...
research
∙
10/28/2011
Backdoors to Acyclic SAT
Backdoor sets, a notion introduced by Williams et al. in 2003, are certa...
research
∙
04/29/2011
Limits of Preprocessing
We present a first theoretical analysis of the power of polynomial-time ...
research
∙
04/21/2011
Algorithms and Complexity Results for Persuasive Argumentation
The study of arguments as abstract entities and their interaction as int...
research
∙
04/14/2011
Augmenting Tractable Fragments of Abstract Argumentation
We present a new and compelling approach to the efficient solution of im...
research
∙
04/14/2011
Backdoors to Tractable Answer-Set Programming
Answer Set Programming (ASP) is an increasingly popular framework for de...
research
∙
04/13/2011
