This is the fourth edition of GWP, following GWP 2021, GWP 2022 and GWP 2023.
It will be a one-day workshop, consisting of 6 invited talks, and finishing with a session for further discussion and open problems.
For the final session of the workshop, we invite short presentations that highlight an open problem or potential area for future research. If you wish to have a 15-minute slot in our workshop, please send an email with a title and short description to andrea.munaro@unipr.it by Monday 30 June 2025. Note that the review of contributions may close earlier if the session is filled.
Lars Jaffke – "F-Branchwidth and Meta Width Measures"
F-Branchwidth is a meta width measure that captures tree-width, co-tree-width, clique-width, mim-width, and several of their interpolations and generalizations through a single framework. While it allows for an infinite number of instantiations, there is a family of eleven equivalence classes of F-branchwidth measures in terms of (asymptotic) expressive power. In this talk, we introduce this framework and its structural properties and discuss some (im-)possibilites of obtaining new tractability results through it. We end on a general discussion of what the perspective of meta width measures can bring to the field.
William Lochet – "Recent developments in contraction decomposition"
Given a graph G and an integer k, a contraction decomposition consists of a partition of the edges of G into k color classes such that the contraction of any one class results in a graph of treewidth O(k). Starting as an extension of Baker's technique, such decompositions have been proven to exist for planar graphs up to H-minor-free graphs, with many algorithmic consequences for approximation and parameterized algorithms.
In this talk, I will talk about recent developments around this technique. The first is how to adapt it to intersection graphs, and then how to build stronger decompositions, where we still have control on the treewidth even if we don't contract all the edges.
Marcin Pilipczuk – "Structural measures of metric spaces"
Abbasi et al. at FOCS 2023 introduced the notion of eps-scatter dimension: an abstract invariant of a metric space that guarantees existence of relatively simple FPT approximation schemes for a wide range of clustering problems. Viewed from an appropriate angle, eps-scatter dimension is the metric equivalent of the semi-ladder index we know from graph theory. Subsequent works defined metric analogs of many tools and invariants we know from structural and algorithmic graph theory, such as weak coloring numbers or uniform quasi-wideness, and showed how to use them algorithmically for classic tasks in metric spaces. In the talk I will survey the results so far and speculate about further directions.
Igor Razgon – "Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width"
We initiate study of width parameters of graphs where the width is large if any (tree or path) decomposition contains a 'large' bag at a 'bad' location. Our motivation for studying such parameters comes from knowledge compilation, in particular, the restriction of the Decomposable Negation Normal Form (DNNF) where the conjunction gates are imbalanced. The concept of imbalanced gates has been first considered in [Lai, Liu, Yin 'New canonical representations by augmenting obdds with conjunctive decomposition', JAIR, 2017]. We consider the gates in the following context.
Free Binary Decision Diagram is a landmark model for representation of Boolean function. If we equip FBDD with decomposable conjunction gates we will obtain Decision DNNF a.k.a. ∧d-FBDD, an important model for tracking performance of SAT solvers with counting. From the univariate perspective the decomposable gates do not add much power as there exists a quasipolynomial simulation of ∧d-FBDD by ordinary FBDD. The things change though if we consider parameterization. In particular, a CNF of primal treewidth k can be represented as 2k · n ∧-D-FBDD and, in general, needs a nΩ(k)-sized FBDD for its representation.
We consider a restriction of ∧d-FBDD where all the conjunction gates are α-imbalanced for some fixed 0 < α < 1. This means that at most one input of each gate depends on more than nα variables. We demonstrate that for representation of CNFs of bounded treewidth such a model needs size n Ω((1-α) √ k). That is, imblanced gates are not strong enough for establishing FPT-sized representation of CNFs of bounded treewidth. The main engine for proving the result is a combinatorial statement considering a family of graphs of max-degree 6 and treewidth at most k and proving that these graphs have pathwidth Ω((1-α) log n √ k) with a big bag having a bad location (the 'badness' of the location depends on α).
We then demonstrate that the idea of location-based width has potential for design of efficient algorithms. For example, the notion of small location-based width that we used above leads to an O(2k · 2nα) algorithm for Independent Set.
The preprint is available at: https://arxiv.org/abs/2505.16012.
Uéverton Souza – "Co-degeneracy and Bondy-Chvátal Closures"
In 1976, Bondy and Chvátal [DM 1976] introduced the notions of graph closures and stability of graph properties. Let ℓ be an integer; the (n+ℓ)-closure, cln+ℓ(G), of a graph G with n vertices is obtained from G by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least n+ℓ until no such pair remains. A graph property Υ defined on all graphs of order n is said to be (n+ℓ)-stable if for any graph G of order n that does not satisfy Υ, the fact that uv is not an edge of G and that G+uv satisfies Υ implies d(u)+d(v)< n+ℓ.
The complexity of deciding graph problems Π on the complement of G considering a parameter p of G, especially for sparse graph parameters such as treewidth and degeneracy, it is an interesting research line. In this talk, we present a systematic study of co-degeneracy (the degeneracy of the complement graph) as a parameter. We develop an algorithmic framework for co-degeneracy parameterization based on the notion of closures for solving problems that are (n+ℓ)-stable for some ℓ bounded by a function of the co-degeneracy. Using such a framework, it is shown that Longest Path, Longest Cycle, and Path Cover are all fixed-parameter tractable when parameterized by co-degeneracy. In addition, we determine the stability of the property of having a cycle cover of size at most r. After that, using our closure framework together with some results and techniques presented in Jansen, Kozma, and Nederlof [WG 2019], we show that Cycle Cover parameterized by co-degeneracy admits a kernel with linear number of vertices. Besides that, we also show that Edge Dominating Set is FPT when parameterized by co-degeneracy.
Meirav Zehavi – "Using Treewidth to Develop Parameterized Algorithms for Geometric Graphs"
This talk surveys a variety of geometric settings in which the goal is to design fast—ideally subexponential—parameterized algorithms. The focus includes visibility graphs, geometric intersection graphs, and planar graphs. A common theme across these scenarios is the use of small treewidth: in each case, the input either is a graph or can be associated with one whose treewidth is suitably bounded, enabling simple and efficient algorithmic solutions.
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