3 papers
cs.DS2026
Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
Robert Ganian, Marlene Gründel
Treewidth is a well-studied decompositional parameter to measure the tree-likeness of a graph. While the propositional satisfiability problem (SAT) is known to be tractable when pa…
cs.LO2026
The Descriptive Complexity of Relation Modification Problems
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz +2
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined p…
cs.AI2026
Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
Robert Ganian, Marlene Gründel, Simon Wietheger
Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formu…