ABSTRACT. Constraint satisfaction problems (CSPs) provide a common modelling language for many application domains. In a CSP, the input is a collection of constraints imposed on a common set of variables, and the goal is to assign values to the variables so that all constraints are satisfied. For example, in reasoning applications, checking the consistency of available data can often be formulated as a CSP. In practice, however, constraint systems are often inconsistent because of noisy data, modelling errors, faulty measurements, conflicting requirements, or other imperfections. This motivates the MinCSP problem: given a CSP instance and a budget k, can we make the instance consistent by deleting at most k constraints? In this talk, I will discuss the complexity of solving almost-satisfiable CSPs, focusing on the parameterized complexity of MinCSPs with respect to the deletion budget k. I will survey dichotomy results, algorithmic techniques, and lower bounds, with applications to problems in spatial and temporal reasoning.

ABSTRACT. The abstract of the talk can be found in the PDF file as requested.

ABSTRACT. Non-clashing teaching, introduced by Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023], is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark of Goldman and Mathias [COLT 1993]. In the past few years, (positive) non-clashing teaching for the concept class of balls in graphs has been thoroughly studied, yielding numerous algorithmic and combinatorial results. This concept class also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph. In this talk, I will survey the complexity landscape of non-clashing teaching in graphs. I will present some of our recent results, including near-tight running time upper and lower bounds for general graphs, parameterized algorithmic and hardness results, and combinatorial bounds for broader graph classes.

ABSTRACT. Gerrymandering, the process of deliberately redistricting via manipulation of boundaries to favor a chosen candidate, is a recurring issue in elections. A standard setting to model voting is when voters and ballot boxes are located in $\mathbb{R}^2$, distances are computed using $\ell_2$-norm, the voting rule is plurality and each voter is assigned to vote at the opened ballot box nearest to them. Eiben et al. [AAAI '20] designed an optimal algorithm for the question where given a set $\mathcal{B}$ of $m$ ballot box locations and a set $\mathcal{V}$ of $n$ voters with known preferences over a set of candidates $\mathcal{C}$, the computational question is to decide if some $k$ ballot boxes can be opened from $\mathcal{B}$ such that a chosen candidate from $\mathcal{C}$ wins in at least $\ell$ of these ballot boxes? Gerrymandering seeks to exploit the fact that \emph{``all ballot boxes are equal"}, i.e., it doesn't matter how few voters voted at a ballot box or how small was the margin of victory as long as your chosen candidate wins. This is reflected in the lower bound construction of Eiben et al. [AAAI '20] where one ballot box gets only 9 votes while another ballot box has more than $(3/4)$-fraction of the $2^{O(k)}$ voters voting in it. In this paper, we study the question of how the complexity of Gerrymandering changes if we enforce a fairness condition that any two opened ballot boxes cannot have a big difference in how many voters are voting in them? Formally, given any integer $\beta\geq 1$, the \fgm problem has the additional condition that the ratio of the number of voters voting in any two of the opened ballot boxes is at most $\beta$. We completely resolve the complexity of \fgm by: \begin{itemize} \item Designing an algorithm running in $(m+n)^{\beta\cdot |\mathcal{C}|\cdot O (\sqrt{k})}$ time \item Obtaining a lower bound that there is no $f(k,n)\cdot m^{o(\sqrt{k})}$ time algorithm (for any computable function $f$) under the Exponential Time Hypothesis (ETH) even when $|\mathcal{C}|=2$. \end{itemize} Our lower bound construction is able to reduce the number of voters $n$ to be $\text{poly}(k)$ whereas Eiben et al. [AAAI '20] required it to be $\text{exp}(k)$.

ABSTRACT. Constraint satisfaction problems with few variables but large domains arise naturally in parameterized algorithms for graph-separation problems and, more broadly, in the study of MinCSPs over finite and temporal domains. As suggested by George Osipov’s morning talk, flow augmentation plays a central role in the tractability classifications for Boolean MinCSPs and for certain temporal MinCSPs, such as MinCSP(<, ≤) and MinCSP(=, ≠). At a high level, flow augmentation reduces these problems to CSP instances with a parameter-bounded number of variables but potentially unbounded domains. Tractability is then obtained by exploiting the particular structure of the resulting constraints. A natural graph-separation problem that remained elusive even after the application of flow augmentation is Directed Multicut with three terminal pairs. Given a digraph D, three ordered pairs of vertices (s_1,t_1), (s_2,t_2), (s_3,t_3), called terminal pairs, and a positive integer k, the task is to determine whether one can delete at most k arcs of D so that, in the resulting digraph, there is no directed path from s_i to t_i for any i in {1, 2, 3}. Directed Multicut has been known, for more than a decade, to be W[1]-hard when the input contains four terminal pairs. However, the parameterized complexity of the three-pair case remained open for a long time; we resolve it affirmatively by giving an FPT algorithm. In this talk, we will walk through the main ideas behind this algorithm. We will see how flow augmentation allows Directed Multicut to be modelled as a CSP with few variables and large domains, and how the resulting CSP can then be solved using a \emph{twin-width}-based win-win argument. More broadly, the talk illustrates how twin-width---a graph parameter introduced in 2020---can capture the structural complexity of constraints arising in bounded-variable CSPs over unbounded domains.

ABSTRACT. Algorithmic meta-theorems establish broad tractability results of the form that every problem expressible in a given logic can be solved efficiently on graph classes with suitable structural properties. A central objective in this area is to identify the exact tractability boundaries for increasingly expressive logics and increasingly general graph classes. For first-order logic, we established that on graph classes closed under taking subgraphs, model checking is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, 2014]. More recently, attention has shifted to the substantially more challenging setting of graph classes closed under taking induced subgraphs, where the precise tractability frontier is still far from understood. At the same time, first-order logic has important expressive limitations, most notably its inability to capture connectivity. To overcome this, we introduced separator logic as a natural extension with significantly greater expressive power and many algorithmic applications [Schirrmacher, Vigny, Siebertz, 2022]. For classes closed under taking subgraphs, we proved that model checking for separator logic is fixed-parameter tractable precisely on classes excluding a fixed topological minor [Pilipczuk et al., 2022]. In this talk, I will survey these developments and present recent progress on algorithmic meta-theorems for expressive logics on structurally restricted graph classes [Mählmann et al., 2026+]. I will then discuss an application to the recently introduced framework of solution discovery [Fellows et al. 2023],  where the goal is not to compute a solution from scratch, but to transform a given initial configuration into a valid solution using as few modification steps as possible.

ABSTRACT. In this talk, I will consider model counting, which asks to output the number of solutions to a given input instance. I will present recent complexity results and a solving approach that employs structural parameters (treewidth) for faster solving. While the algorithm provides a theoretical bound, a direct implementation is, unsurprisingly, practically infeasible. Therefore, we turn our attention to a more practical exploitable direction. Finally, I will illustrate practical applications of counting to analyze and navigate solution spaces, including directions that focus on counting for decision spaces rather than entire solution spaces, significantly improving complexity.