ABSTRACT. We survey parameterized approximation results for optimization versions of constraint satisfaction problems (Max-CSPs). This includes approximation schemes for such fundamental problems as Max-SAT that run in FPT time for various structural parameters of the instance incidence graph. We further give examples for the pivotal role of CSPs in proofs of parameterized inapproximability.

ABSTRACT. We study the Kemeny Rank Aggregation (KRA) problem, a well- studied problem lying in the intersection of order theory and social choice theory. Using a problem from order theory called Completion of an Ordering to model KRA, we give an FPT algorithm parameterized by the interval width of the unanimity order of the input votes. We also relate the interval width of the unanimity order to the maximum range parameter and improve on previous parameterized algorithms. Then, we combine the techniques developed for the FPT algorithm with the paradigm of diversity of solutions. This recent trend of research in artificial intelligence has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. In this settings, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of ag- gregation over linearly ordered votes, and in the more general setting where votes are partially ordered. This work is based on join works with Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Petra Wolf [1, 2].

ABSTRACT. Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. The equations are defined over Euclidean domains -- an abstract algebraic structure generalizing finite and infinite fields including the rationals, the ring of integers, and many other structures. We find that the problem is W[1]-hard when three or more variables are allowed in an equation. The remaining case with two-variable equations is more interesting since it generalizes many eminent graph separation problems like Bipartization, Multiway Cut and Multicut parameterized by the solution size. We provide an fixed-parameter tractable algorithm for this case. On the technical side, we introduce the notion of important balanced subgraphs and an fpt algorithm for their enumeration. The method is used as a more efficient alternative to the sampling of important separators [Marx and Razgon, SICOMP'14]. Further, we use recent results on parameterized MinCSP [Kim et al., SODA'21] to solve a generalization of Multicut with disjunctive cut requests.

The talk is based on joint (unpublished) work with Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, and Magnus Wahlström.

ABSTRACT. Quantified Boolean Formulas (QBFs) are propositional formulas with universal and existential quantification over truth values. The satisfiability problem of QBFs (QSAT) is PSPACE-complete and lends itself to natural encodings for a range of problems in AI and formal verification.QSAT is well known to be FPT parameterized by the number of quantifier alternations and treewidth of the input formula, but PSPACE-hard parameterized by treewidth alone.This matches an intuition that decomposition techniques for SAT can typically be adapted when quantifiers in the prefix are ordered the right way, but break down once the ordering is permuted.In hopes of obtaining new insights into the compositional structure of QSAT, we consider more restrictive parameters than treewidth, and present preliminary results.

ABSTRACT. Decision trees (DT) have become an invaluable tool for providing interpretable models of data in various areas of computer science. Probably the most fundamental computational task in the context of DTs is to learn DTs from data. Here one usually aims at finding small trees since those are easier to interpret and require fewer decisions. Although learning a smallest DTs is known to be NP-hard, the problem’s behavior under natural restrictions on the data is widely open.  To improve our understanding, we provide the first parameterized complexity analysis of the problem.

Our starting point are hardness results which show that the problem is not fixed-parameter tractable when parameterized by solution size alone (i.e., size or depth of the obtained DT). We then identify natural additional and necessary restrictions (modelled by parameters) to achieve fixed-parameter tractability. Our results provide a comprehensive complexity map for the considered parameters, exhibiting the significance of each parameter. The fixed-parameter tractability result is based on a new algorithmic technique that is of independent interest. In particular, we show that learning DTs is fixed-parametertractable parameterized by size (or depth) and an additional parameter that can be shown to behave well in practise. We complement our algorithmic results with lowerbounds that allow us to arrive at an comprehensive complexity map w.r.t. all considered parameterizations.

ABSTRACT. A knockout tournament is a standard format of competition, ubiquitous in sports, elections, and decision-making. In this context, one central question, captured by the Tournament Fixing Problem, is whether the tournament can be conducted in a way that makes our favorite player win. In this talk, we will discuss the state-of-the-art, with emphasis on parameterized analysis, of the Tournament Fixing problem and its variants, as well as take a closer look at a few recent advances.