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

Most optimization problems defined on graphs are computationally hard. For such problems it is natural to restrict the input and ask:

For which graph classes does the problem become efficiently solvable and for which graph classes does it stay hard?

Knowing that a graph has small "width" (for example, treewidth, clique-width, mim-width) has proven to be highly useful for designing efficient algorithms for many well-known problems, such as Feedback Vertex Set, Graph Colouring and Independent Set. That is, boundedness of width enables the application of a problem-specific dynamic programming algorithm or a meta-theorem to solve a certain problem. However, for many graph classes it is not known if the class has small width for some appropriate width parameter. This has resulted in ad-hoc efficient algorithms for special graph classes that may unknowingly make use of the fact that the graph classes under consideration have small width. More generally speaking, rather than solving problems one by one and graph-class by graph-class, the focus of our satellite workshop is:
  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.
For this purpose we aim to bring together researchers from Discrete Mathematics (structure) and Theoretical Computer Science (algorithms).

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

Programme

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

9:30 - 10:30: intro/welcome and invited talk
10:30 - 11:00: break
11:00 - 11:45: invited talk
11:45 - 12:30: invited talk
12:30 - 14:00: break
14:00 - 14:45: invited talk
14:45 - 15:30: invited talk
15:30 - 16:00: break
16:00 - 16:45: invited talk
16:45 - 18:00: open problem session

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 MSO1 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 nO(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 C is said to be delineated if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if 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 C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when 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 – TBC

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 – TBC

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