research
∙
05/23/2023
Parameterized Complexity Classification for Interval Constraints
Constraint satisfaction problems form a nicely behaved class of problems...
share
research
∙
04/27/2023
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
The QSAT problem, which asks to evaluate a quantified Boolean formula (Q...
research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
11/18/2022
Computational Short Cuts in Infinite Domain Constraint Satisfaction
A backdoor in a finite-domain CSP instance is a set of variables where e...
research
∙
08/04/2022
Almost Consistent Systems of Linear Equations
Checking whether a system of linear equations is consistent is a basic c...
research
∙
02/16/2022
SAT Backdoors: Depth Beats Size
For several decades, much effort has been put into identifying classes o...
research
∙
01/27/2022
An Algorithmic Framework for Locally Constrained Homomorphisms
A homomorphism f from a guest graph G to a host graph H is locally bijec...
research
∙
11/15/2021
Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises
An influential 1990 paper of Hochbaum and Shanthikumar made it common wi...
research
∙
07/03/2021
Solving Infinite-Domain CSPs Using the Patchwork Property
The constraint satisfaction problem (CSP) has important applications in ...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
research
∙
12/07/2019
Parameterized Algorithms for MILPs with Small Treedepth
Solving (mixed) integer linear programs, (M)ILPs for short, is a fundame...
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
∙
07/28/2019
Parameterized Pre-coloring Extension and List Coloring Problems
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the p...
research
∙
09/03/2018
The Complexity Landscape of Decompositional Parameters for ILP
Integer Linear Programming (ILP) can be seen as the archetypical problem...
research
∙
08/21/2018
Group Activity Selection with Few Agent Types
The Group Activity Selection Problem (GASP) models situations where a gr...
research
∙
08/10/2018
The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
This paper revisits the classical Edge Disjoint Paths (EDP) problem, whe...
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
∙
11/06/2017
Small Resolution Proofs for QBF using Dependency Treewidth
In spite of the close connection between the evaluation of quantified Bo...
research
∙
11/06/2017
On Structural Parameterizations of the Edge Disjoint Paths Problem
In this paper we revisit the classical Edge Disjoint Paths (EDP) problem...
research
∙
06/30/2016
Clique-Width and Directed Width Measures for Answer-Set Programming
Disjunctive Answer Set Programming (ASP) is a powerful declarative progr...
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
∙
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
∙
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
∙
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
∙
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