Tutorials

The workshop will feature four invited tutorials:

• Édouard Bonnet: Twin-width and parameterized complexity (beyond what you may have heard repeatedly)
  Abstract: We propose several open questions at the interface of twin-width and parameterized complexity,
  and present their context, possible obstacles, and what we believe to be relevant background to attempt solving them.
   
  (If you are completely new to twin-width, watching an introductory talk to the topic such as
  https://www.youtube.com/watch?v=BddeeHWRX_g&ab_channel=FAS,
  https://www.youtube.com/watch?v=d67WI0I8urs&ab_channel=IBSDiscreteMathematicsGroup, 
  https://www.youtube.com/watch?v=P0_2ya3et24,
  while not being necessary, can only help.)
•  
• Sándor Kisfaludi‑Bak: Separating intersection graphs in Euclidean and hyperbolic space
  Abstract: Geometric intersection graphs are commonly used to model real-world networks. A frequently used tool for solving problems on such graphs is a separator: usually, a small subset whose removal cuts the graph into two independent parts that have roughly the same size. Separation is a common first step in being able to solve problems, regardless of our goals, which can range from exact subexponential algorithms, parameterized algorithms, or even approximations. In this tutorial, we will see some techniques that have been successful in separating intersection graphs that are defined using various objects in Euclidean space. We will then introduce hyperbolic intersection graphs that are also used for modeling real-world networks. After the computer-scientist-friendly intro, we will start exploring separators on such graphs, as well as some natural graph parameters related to hyperbolic spaces.
•  
• Marcin Pilipczuk: Applications of flow-augmentation
  Abstract: In a recent paper,  we show a ƒflow-augmentation algorithm in directed graphs: th‘ere exists a polynomial-time algorithm that, given a directed graph G, two integers s, t ∈ V (G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2^{−poly(k)} the set Z becomes a minimum st-cut in the resulting graph. This tool allows us to prove fixed-parameter tractability of two problems, whose parameterized complexity status was repeatedly posed as open problems:
  1. Chain SAT, defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17]
  2. a number of weighted variants of classic directed cut problems, such as Weighted st-Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT.
  In subsequent work, we show this tool is the last missing piece to obtain a FPT vs W[1]-hardness dichotomy for Min Unsat CSP problems for boolean CSPs over a binary alphabet, parameterized by the number of unsatisfied constaints (i.e., delete at most k constraints to get a satisfiable instance). In the talk I will introduce the flow-augmentation tool (without a proof) and discuss its various applications.
•  
• Michał Włodarczyk: H-Elimination distance and H-treewidth: FPT algorithms with hybrid graph measures
  Abstract: For a graph class H (e.g. bipartite or planar graphs) we can consider several measures capturing how far a graph G is from the class H. The simplest one is the H-deletion number: the minimal number of vertices that has to be deleted from G to make it belong to H. Several problems studied in the parameterized complexity can be phrased as H-deletion, that is, computation of the H-deletion number, e.g., Odd Cycle Transversal or Vertex Planarization. Existing FPT algorithms for these problems either focus on the parameterization by the size of the deletion set, detecting graphs of H-deletion number at most k in time f(k)*n^O(1), or width parameterizations, finding arbitrarily large optimal deletion sets in time f(w)*n^O(1) for some width measure w like treewidth.
   
  A recent trend in parameterized complexity considers hybrid graph measures which are relaxations of either treedepth of treewidth, that treat subgraphs from the class H as simple. These measures are called H-eliminations distance and H-treewidth and can be instantiated for any hereditary graph class H. They can be arbitrarily much smaller than both the H-deletion number and treedepth/treewidth. I will give an introduction to the hybrid graph measures and cover the recent results about the FPT algorithms for computing H-eliminations distance/H-treewidth and the FPT algorithms for different problems parameterized by these measures, focusing on H-deletion.

The main part of the programme devoted to solving open problems. The tentative list of open problems is avalailable here:

PARUW3 Open Problems

If you want to add your problem, please write it in the form sent out by email.