Graph Width Parameters: from Structure to Algorithms (GWP 2022)

Satellite Workshop of ICALP 2022
Monday 4 July 2022

This is the second edition of GWP, following GWP 2021.

Aim and Scope

1. discovering general properties of graph classes from which we can determine the tractability or hardness of graph problems, and
2. discovering which graph problems can be solved efficiently on graph classes of bounded width.

Format

This will be a hybrid workshop: participants can attend either in person, or remotely via Zoom.

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 10-minute slot in our workshop, please send an email with a title and short description to a.munaro@qub.ac.uk by Monday 27 June 2022. Please indicate if you plan to present your open problem in-person or online. Note that the review of contributions may close earlier if the session is filled.

Registration

To attend in-person, register for the workshops day of ICALP 2022, as detailed here.

For free online participation, please fill in this form. The deadline for online registration is Friday 1 July.

Speakers

• Benjamin Bergougnoux, Department of Informatics, University of Bergen, Norway.
• Édouard Bonnet, LIP, ENS Lyon, France.
• Clément Dallard, FAMNIT, University of Primorska, Koper, Slovenia.
• Zdeněk Dvořák, Computer Science Institute, Charles University, Prague, Czech Republic.
• Paloma T. Lima, Computer Science Department, IT University of Copenhagen, Denmark.
• Sophie Spirkl, Department of Combinatorics and Optimization, University of Waterloo, Canada.

Programme

All times are in the Central European Summer Timezone (CEST), UTC+2, GMT+2.

Abstracts

Benjamin Bergougnoux – "A Logic-Based Algorithmic Meta-Theorem for Mim-Width"

Joint work with Jan Dreier and Lars Jaffke.

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (AC DN for short) which extends existential MSO₁ with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed AC DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well.

Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

Édouard Bonnet – "Twin-width delineation and win-wins"

A graph class $\mathcal{C}$ is said to be delineated if for every hereditary closure $\mathcal{D}$ of a subclass of $\mathcal{C}$, it holds that $\mathcal{D}$ has bounded twin-width if and only if $\mathcal{D}$ is monadically dependent (i.e., cannot express every graph by means of a first-order transduction). An effective strengthening of delineation for a class $\mathcal{C}$ implies that tractable FO model checking on $\mathcal{C}$ is perfectly understood: On hereditary closures of subclasses $\mathcal{D}$ of $\mathcal{C}$, FO model checking on $\mathcal{D}$ is fixed-parameter tractable (FPT) exactly when $\mathcal{D}$ has bounded twin-width. We explore which classes are delineated and which are not. Along the same lines, we present FPT algorithms for some W[1]-hard problems in general graphs, on classes of unbounded twin-width, via win-win arguments.

Clément Dallard – "Introduction to tree-independence number"

Tree decompositions are a useful data structure for designing dynamic programming algorithms for graph problems. Usually, in order to obtain efficient algorithms, one looks for a tree decomposition of the input graph that minimizes some measure on the subgraphs induced by the bags. When this measure is the number of vertices, we obtain the notion of treewidth. In this talk, the considered measure is the independence number. More precisely, the independence number of a tree decomposition of a graph is the smallest integer k such that each bag induces a subgraph with independence number at most k. The tree-independence number of a graph G is then defined as the minimum independence number over all tree decompositions of G. Given a tree decomposition with bounded independence number, the Maximum Weight Independent Set and several related problems can be solved in polynomial time.

We review some results about computing tree decompositions with bounded independence number, their algorithmic applications, and the relationship with (tw,ω)-boundedness.

Zdeněk Dvořák – "On fractional treewidth-fragility"

A graph G is fractionally f-treewidth-fragile if for every k and every assignment w of weights to vertices, there exists a subset X of vertices of G such that w(X) ≤ w(G) / k and G − X has treewidth at most f(k); i.e., the treewidth of G can be reduced to constant by removing a small fraction of the weight. A class of graphs is fractionally treewidth-fragile if there exists a function f such that all graphs from the class are fractionally f-treewidth-fragile. We survey the graph classes that are fractionally treewidth-fragile and describe applications of this notion in design of approximation algorithms.

Paloma T. Lima – "A survey on coloring problems parameterized by width"

Some variants of the Graph Coloring problem were defined to study the worst-case behaviour of heuristics to find optimal proper colorings. This is the case of b-Coloring, related to a color-suppressing heuristic, as well as Grundy Coloring, associated with the greedy (first-fit) heuristic. These problems have been widely studied through the lenses of parameterized complexity. In this talk I will survey some recent results on these problems when parameterized by width measures, and talk about related open problems.

Sophie Spirkl – "Induced subgraphs and treewidth"

The results of Robertson and Seymour tell us which subgraphs of large treewidth are always present in graphs of large treewidth: subdivisions of walls. The analogous question for induced subgraphs is still open, and constructions of Sintiari and Trotignon, and of Davies, show that the answer for induced subgraphs is more complicated. I will talk about some recent results in this area. Based on joint work with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, and Kristina Vušković.

Organisers

Flavia Bonomo
University of Buenos Aires
Buenos Aires, Argentina

Nick Brettell
Victoria University of Wellington
Wellington, New Zealand

Andrea Munaro
Queen's University Belfast
Belfast, UK

Daniel Paulusma
Durham University
Durham, UK