This is the third edition of GWP, following GWP 2021 and GWP 2022.
Hans L. Bodlaender – "Classes of parameterized (in)tractability and graph width parameters"
Between the complexity classes FPT and XP is a rich landscape of parameterized complexity classes. In this talk, a number of such complexity classes are surveyed. We will see how different graph width parameters can frequently be associated with different parameterized complexity classes, with several graph problems complete for the class with this width as parameter. As running example, we discuss the complexity of Binary CSP under different parameterizations.
Esther Galby – "Double-Exponential Lower Bounds for Parameterisations by Treewidth"
Courcelle's celebrated Theorem states that problems expressible in the language of monadic second order logic can be solved in time f(w) · n on graphs of treewidth w. While this result readily gives algorithms for numerous problems, the running-time is notoriously bad as the function f is an exponential tower whose height is linear in the quantifier alternation of the formula. As this bound is likely to be much higher than optimal, a lot of effort has been put on providing tighter bounds on the dependency on the treewidth. For a majority of problems, it has been shown that this dependency is a single-exponential, that is, of the form 2O(w), and very few problems are known to have a worst dependency. In this talk, we will present the short list of problems that require a double-exponential dependency on the treewidth, in which, surprisingly, appears the NP-complete problem known as Metric Dimension.
Michael Lampis – "Quantifier Alternations and Graph Widths"
In this talk we focus on a disturbing phenomenon that affects most (though not all) of the typically standard width parameters: when one considers problems with an alternating quantifier structure, each additional quantifier entails an exponential increase in the running time. We describe this phenomenon in two settings. First, we consider concrete problems with an alternating quantifier structure by looking at problems complete for the second level of the polynomial hierarchy, such as ∃∀-SAT. We explain why such problems have a double-exponential parameter dependence on treewidth and related measures, and what happens if even more quantifiers are added. Second, we revisit the same phenomenon from the point of view of algorithmic meta-theorems, and explain why the exponential cost of alternating quantifiers is the main obstacle to obtaining meta-theorems faster than Courcelle's. Finally, we make some connections between the alternating quantifier phenomenon in structural parameterized complexity and its counterparts in neighboring areas, such as structural graph theory and classical computational complexity.
Roohani Sharma – "Twinwidth and flow-augmentation: the case of Directed Multicut with 3 terminal pairs"
Twinwidth is a fairly new width measure which was introduced by Bonnet, Kim, Thomassé, Watrigant [FOCS 2020], and that aims to generalize the class of co-graphs. Within the last three years of its introduction, already a very strong theory has been build around it, but in this talk we not delve into surveying this theory. Rather, we exhibit an arguably non-obvious scenario, where the theory of twinwidth built so far has proven useful.
In particular, we consider the Directed Multicut problem with three terminal pairs, and show that it is fixed-parameter tractable (FPT) with respect to the solution size [SODA 2023]. This problem was the last missing piece in understanding the parameterized complexity of arguably, the most fundamental NP-hard cut problems. To design an FPT algorithm for this problem, we use some fundamental theorems for twinwidth, together with directed flow-augmentation. The later is again a new tool given by Kim, Kratsch, Pilipczuk, Wahlström [STOC 2022] that has been proved extremely useful in understanding the parameterized complexity of cut problems.
As a by-product of designing the above FPT algorithm, we also conclude that the notion of twin-width helps to capture a tractable fragment of the Permutation CSP problem.
Kirill Simonov – "Above-Guarantee Parameterizations: Extremal Combinatorics meets Algorithms"
There is now a growing scope of works related to finding substructures (i.e., paths/cycles, cliques, trees) in graphs when parameterized not by the desired size of the structure, but by an "offset" of the size from an existential combinatorial bound. While questions of this kind are not usually stated in terms of the commonly studied width parameters, there are nonetheless rich structural properties arising between the original combinatorial results and the resulting parameterized algorithms.
In this talk, I will survey recent results in this area, with a particular emphasis on the Longest Path/Cycle problems. A prominent example is the 2δ(G) guarantee for the length of a cycle given by Dirac's theorem, which was recently lifted to an FPT algorithm finding a cycle of length at least 2δ(G) + k, where k is the parameter [Fomin, Golovach, Sagunov, Simonov; SODA 2022]. The central tool in this result is the so-called Dirac's decomposition, which also has further algorithmic applications. Another direction is finding detours: while the problem is known to be FPT in undirected graphs, the directed case is still open except for a few graph classes where 2-Disjoint Paths can be solved in polynomial time [Jacob, Włodarczyk, Zehavi; 2023].
Michał Włodarczyk – "Efficient algorithms with H-treewidth"
H-treewidth generalizes treewidth by treating subgraphs from the graph class H as 'simple' and allowing the bags in a decomposition to have unbounded size as long as they induce graphs from H. While H-treewidth can extend the horizon of tractability for various problems, there are two algorithmic challenges on the way of getting 'reasonable' running times. The first one is how to compute a decomposition of a graph promised to have low H-treewidth and the second is how to exploit the decomposition for solving problems like H-Vertex-Deletion. I will begin with a survey on what happened in this area in the last years, explaining two different approaches to these challenges. I will then move on to our recent result about computing an almost optimal-width decomposition efficiently and discuss several open problems.
Flavia Bonomo
University of Buenos Aires
Buenos Aires, Argentina
Nick Brettell
Victoria University of Wellington
Wellington, New Zealand
Andrea Munaro
University of Parma
Parma, Italy
Daniel Paulusma
Durham University
Durham, UK