Max Bannach
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Max Bannach has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Till Tantau
Universität zu Lübeck
6 shared publications - Markus Hecher
University of Potsdam
5 shared publications - Sebastian Berndt
Technische Hochschule Lübeck
4 shared publications - Jai Grover
ESA—Advanced Concepts and Studies Office, European Space Research Technology Centre (ESTEC), Keplerlaan 1, Postbus 299, NL-2200AG Noordwijk, Netherlands
2 shared publications - Malte Skambath
Department of Computer Science Kiel University Germany
2 shared publications - Alexander Hadjiivanov
Advanced Concepts Team, European Space Research & Technology Centre, Noordwijk, The Netherlands
1 shared publication
Latest Publications
- Open Access
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 78-88
Counting Solutions Under Cardinality Constraints: Structure Counts in Counting
Model counting is a powerful extension of constraint reasoning that, instead of finding a solution to a constraint system, allows to identify the number of such solutions. Cardinality constraints are used to filter solutions of a certain quality by restricting the number of elements that can be added to the solution. Naturally, one would like to combine both in order to count the number of solutions of good quality. Unfortunately, the two concepts do not get along so well as (1) cardinality constraints may not be parsimonious (due to auxiliary variables, the system’s number of solutions may change in an uncontrolled way) and (2) such constraints may destroy structural properties, which are crucial for the performance of modern solvers. This article provides a systematic study of existing cardinality constraints in the light of model counting, observing that none of them are both, parsimonious and treewidth-preserving. We present structure-aware cardinality constraints that are parsimonious and guaranteed to increase the input’s treewidth only in a controlled way. Detailed experiments reveal that our encodings outperform existing ones.
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 78-88
Open AccessCounting Solutions Under Cardinality Constraints: Structure Counts in Counting
Model counting is a powerful extension of constraint reasoning that, instead of finding a solution to a constraint system, allows to identify the number of such solutions. Cardinality constraints are used to filter solutions of a certain quality by restricting the number of elements that can be added to the solution. Naturally, one would like to combine both in order to count the number of solutions of good quality. Unfortunately, the two concepts do not get along so well as (1) cardinality constraints may not be parsimonious (due to auxiliary variables, the system’s number of solutions may change in an uncontrolled way) and (2) such constraints may destroy structural properties, which are crucial for the performance of modern solvers. This article provides a systematic study of existing cardinality constraints in the light of model counting, observing that none of them are both, parsimonious and treewidth-preserving. We present structure-aware cardinality constraints that are parsimonious and guaranteed to increase the input’s treewidth only in a controlled way. Detailed experiments reveal that our encodings outperform existing ones.
- 8 June 2025
- Published by Springer Nature
- p. 72-90
Strong Structural Bounds for MaxSAT: The Fine Details of Using Neuromorphic and Quantum Hardware Accelerators
- 8 June 2025
- Published by Springer Nature
- p. 72-90
Strong Structural Bounds for MaxSAT: The Fine Details of Using Neuromorphic and Quantum Hardware Accelerators
- Open Access
#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF) is complete for #P under Turing reductions. On the other hand, #DNF $\in$ spanL and spanL $\not\subseteq$ #P unless NL = NP. Hence, the class of functions logspace-reducible to #DNF is a strict subset of #P under plausible complexity-theoretic assumptions. By contrast, we show that two calls to a (restricted) #2DNF oracle suffice to capture gapP, namely, that the logspace many-one closure of the subtraction between the results of two #2DNF calls is gapP. Because #P $\not\subseteq$ gapP, #P is strictly contained between one and two #2DNF oracle calls. Surprisingly, the propositional formulas needed in both calls are linear-time computable, and the reduction preserves interesting structural as well as symmetry properties, leading to algorithmic applications. We show that a single subtraction suffices to compensate for the absence of negation while still capturing gapP, i.e., our results carry over to the monotone fragments of #2SAT and #2DNF. Since our reduction is linear-time, it preserves sparsity and, as a consequence we obtain a sparsification lemma for both #2SAT and #2DNF. This has only been known for kSAT with k $\geq$ 3 and respective counting versions. We further show that both #2DNF calls can be combined into a single call if we allow a little postprocessing (computable by AC0- or TC0-circuits). Consequently, we derive refined versions of Toda's Theorem: PH $\subseteq$ [#MON2SAT]$^{log}_{TC0}$ = [#MON2DNF]$^{log}_{TC0}$ and PH $\subseteq$ [#IMPL2SAT]$^{log}_{AC0}$. Our route to these results is via structure-aware reductions that preserve parameters like treewidth up to an additive overhead. The absence of multiplicative overhead indeed yields parameterized SETH-tight lower bounds.Open Access#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF) is complete for #P under Turing reductions. On the other hand, #DNF $\in$ spanL and spanL $\not\subseteq$ #P unless NL = NP. Hence, the class of functions logspace-reducible to #DNF is a strict subset of #P under plausible complexity-theoretic assumptions. By contrast, we show that two calls to a (restricted) #2DNF oracle suffice to capture gapP, namely, that the logspace many-one closure of the subtraction between the results of two #2DNF calls is gapP. Because #P $\not\subseteq$ gapP, #P is strictly contained between one and two #2DNF oracle calls. Surprisingly, the propositional formulas needed in both calls are linear-time computable, and the reduction preserves interesting structural as well as symmetry properties, leading to algorithmic applications. We show that a single subtraction suffices to compensate for the absence of negation while still capturing gapP, i.e., our results carry over to the monotone fragments of #2SAT and #2DNF. Since our reduction is linear-time, it preserves sparsity and, as a consequence we obtain a sparsification lemma for both #2SAT and #2DNF. This has only been known for kSAT with k $\geq$ 3 and respective counting versions. We further show that both #2DNF calls can be combined into a single call if we allow a little postprocessing (computable by AC0- or TC0-circuits). Consequently, we derive refined versions of Toda's Theorem: PH $\subseteq$ [#MON2SAT]$^{log}_{TC0}$ = [#MON2DNF]$^{log}_{TC0}$ and PH $\subseteq$ [#IMPL2SAT]$^{log}_{AC0}$. Our route to these results is via structure-aware reductions that preserve parameters like treewidth up to an additive overhead. The absence of multiplicative overhead indeed yields parameterized SETH-tight lower bounds. - 28 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
On Weighted Maximum Model Counting: Complexity and Fragments
Maximum model counting $(\text{MAX}\#\exists \text{SAT})$ is a recently introduced extension of projected model counting $(\#\exists \text{SAT})$ that maximizes over a set of variables $X$ the number of assignments over a set $Y$ that can be extended to a satisfying assignment over $Z$. It is known that $\text{MAX}\#\exists \text{SAT}$ also generalizes weighted $\#\exists \text{SAT}$ and MAXSAT if weights are introduced to the problem. However, for the latter a non-trivial gadget is needed. We propose a more generic weighting scheme that evaluates a fitness term and a probability term simultaneously. In this setting, $\text{MAX}\#\exists \text{SAT}$ extends weighted MAXSAT and $\#\exists \text{SAT}$ without the need of gadgets. As MAXSAT is the canonical problem of cost-optimal reasoning and $\#\exists \text{SAT}$ can be seen as canonical problem of probabilistic reasoning, $\text{MAX}\# 3\text{SAT}$ with the proposed weighting scheme naturally fills the role as canonical problem for cost-optimal probabilistic reasoning. We study the problem from a complexity-theoretic point of view for unary weights and prove that the decision version is $\mathrm{D}_{2}^{\mathrm{P}}{-}$ complete. We then focus on structural parameters and provide an ETH lower bound with respect to the inputs treewidth, as well as a treewidth-aware reduction from $\text{MAX}\#\exists \text{SAT}$ to $\text{MAX}\#\exists \text{SAT}$.- 28 October 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
On Weighted Maximum Model Counting: Complexity and Fragments
Maximum model counting $(\text{MAX}\#\exists \text{SAT})$ is a recently introduced extension of projected model counting $(\#\exists \text{SAT})$ that maximizes over a set of variables $X$ the number of assignments over a set $Y$ that can be extended to a satisfying assignment over $Z$. It is known that $\text{MAX}\#\exists \text{SAT}$ also generalizes weighted $\#\exists \text{SAT}$ and MAXSAT if weights are introduced to the problem. However, for the latter a non-trivial gadget is needed. We propose a more generic weighting scheme that evaluates a fitness term and a probability term simultaneously. In this setting, $\text{MAX}\#\exists \text{SAT}$ extends weighted MAXSAT and $\#\exists \text{SAT}$ without the need of gadgets. As MAXSAT is the canonical problem of cost-optimal reasoning and $\#\exists \text{SAT}$ can be seen as canonical problem of probabilistic reasoning, $\text{MAX}\# 3\text{SAT}$ with the proposed weighting scheme naturally fills the role as canonical problem for cost-optimal probabilistic reasoning. We study the problem from a complexity-theoretic point of view for unary weights and prove that the decision version is $\mathrm{D}_{2}^{\mathrm{P}}{-}$ complete. We then focus on structural parameters and provide an ETH lower bound with respect to the inputs treewidth, as well as a treewidth-aware reduction from $\text{MAX}\#\exists \text{SAT}$ to $\text{MAX}\#\exists \text{SAT}$.- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 21-22
The Space Optimization Competition: Third Edition
The organizers of the third Space Optimization Competition (SpOC)1 give a brief overview of the competition. We lay out the timeline and discuss administrative decisions. As was common in previous editions, the competition consists of three problems. We present them swiftly and provide their scientific background and motivation.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 21-22
Open AccessThe Space Optimization Competition: Third Edition
The organizers of the third Space Optimization Competition (SpOC)1 give a brief overview of the competition. We lay out the timeline and discuss administrative decisions. As was common in previous editions, the competition consists of three problems. We present them swiftly and provide their scientific background and motivation.
- 19 November 2023
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 78, 673–707
On the Parallel Parameterized Complexity of MaxSAT Variants
In the maximum satisfiability problem (max-sat) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versions of max-sat and provide the first constant-time algorithms parameterized either by the solution size or by the allowed excess relative to some guarantee. For the dual parameterized version where the parameter is the number of clauses we are allowed to leave unsatisfied, we present the first parallel algorithm for max-2sat (known as almost-2sat). The difficulty in solving almost-2sat in parallel comes from the fact that the iterative compression method, originally developed to prove that the problem is fixed-parameter tractable at all, is inherently sequential. We observe that a graph flow whose value is a parameter can be computed in parallel and develop a parallel algorithm for the vertex cover problem parameterized above the size of a given matching. Finally, we study the parallel complexity of max-sat parameterized by the vertex cover number, the treedepth, the feedback vertex set number, and the treewidth of the input’s incidence graph. While max-sat is fixedparameter tractable for all of these parameters, we show that they allow different degrees of possible parallelization. For all four we develop dedicated parallel algorithms that are constructive, meaning that they output an optimal assignment – in contrast to results that can be obtained by parallel meta-theorems, which often only solve the decision version.
- 19 November 2023
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 78, 673–707
On the Parallel Parameterized Complexity of MaxSAT Variants
In the maximum satisfiability problem (max-sat) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versions of max-sat and provide the first constant-time algorithms parameterized either by the solution size or by the allowed excess relative to some guarantee. For the dual parameterized version where the parameter is the number of clauses we are allowed to leave unsatisfied, we present the first parallel algorithm for max-2sat (known as almost-2sat). The difficulty in solving almost-2sat in parallel comes from the fact that the iterative compression method, originally developed to prove that the problem is fixed-parameter tractable at all, is inherently sequential. We observe that a graph flow whose value is a parameter can be computed in parallel and develop a parallel algorithm for the vertex cover problem parameterized above the size of a given matching. Finally, we study the parallel complexity of max-sat parameterized by the vertex cover number, the treedepth, the feedback vertex set number, and the treewidth of the input’s incidence graph. While max-sat is fixedparameter tractable for all of these parameters, we show that they allow different degrees of possible parallelization. For all four we develop dedicated parallel algorithms that are constructive, meaning that they output an optimal assignment – in contrast to results that can be obtained by parallel meta-theorems, which often only solve the decision version.
- Open Access
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.
Open AccessPolynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.
- Open Access
- 22 June 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (11) , 3459-3488
Dynamic Kernels for Hitting Sets and Set Packing
Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size $$k^d$$ (which is a polynomial as d is a constant), and they do so in time $$m\cdot 2^d {\text {poly}}(d)$$ for a small polynomial $${\text {poly}}(d)$$ (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size- $$k^d$$ kernel. This paper presents a deterministic solution with worst-case time $$3^d {\text {poly}}(d)$$ for updating the kernel upon inserts and time $$5^d {\text {poly}}(d)$$ for updates upon deletions. These bounds nearly match the time $$2^d {\text {poly}}(d)$$ needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times $$O(c^k)$$ where $$c = d - 1 + O(1/d)$$ equals the best base known for the static setting.- 22 June 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (11) , 3459-3488
Open AccessDynamic Kernels for Hitting Sets and Set Packing
Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size $$k^d$$ (which is a polynomial as d is a constant), and they do so in time $$m\cdot 2^d {\text {poly}}(d)$$ for a small polynomial $${\text {poly}}(d)$$ (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size- $$k^d$$ kernel. This paper presents a deterministic solution with worst-case time $$3^d {\text {poly}}(d)$$ for updating the kernel upon inserts and time $$5^d {\text {poly}}(d)$$ for updates upon deletions. These bounds nearly match the time $$2^d {\text {poly}}(d)$$ needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times $$O(c^k)$$ where $$c = d - 1 + O(1/d)$$ equals the best base known for the static setting. - Open Access
- 27 January 2022
- Published by MDPI AG in Algorithms
- Vol. 15 (2) , 42
Recent Advances in Positive-Instance Driven Graph Searching
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.
- 27 January 2022
- Published by MDPI AG in Algorithms
- Vol. 15 (2) , 42
Open AccessRecent Advances in Positive-Instance Driven Graph Searching
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.