Algorithms with Small Separations acKnowledged: graphs and linear matroids – ASSK

Our work hinge on a multitude of concept and techniques in graph/matroid theory, algorithms design and logic.

- In joint-work with Édouard Bonnet, Colin Geniet, Stéphan Thomassé and Rémi Watrigant, we introduced a new graph invariant twin-width. In a series of papers, we discover that twin-width is a powerful as well as very natural invariant which captures a wide range of classic graph classes, especially those graph recursively decomposable along small separations such as small rank-width and tree-width, and properties that hold in those classes.

- In a joint-work with Stefan Kratsch, Marcin Pilipczuck, and Magnus Wahlström, we presented a new technique for designing fixed- parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) (s,t)-cut of cardinality at most k in an undirected graph G with designated terminals s and t. We applied our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem called Coupled Min-Cut.

- We gave improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a stream. The family of constraints we consider generalizes both the intersection of p arbitrary matroid constraints and p-uniform hypergraph matching.

- Robertson and Seymour (1983) proved that for every tree T , the class of graphs that do not contain T as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree T, the class of graphs that do not contain T as a pivot-minor has bounded linear rank-width. We prove that this statement is false whenever T is a tree that is not a caterpillar. We are also able to give partial confirmation of this conjecture

The central questions that ignited this project are the following.

A. For which problems decompositions based on dense separation concept help to obtain efficient algorithms?
B. Is there a unified framework that encompasses existing techniques and concepts for separations problems, and can we use it to tackle the open questions?

The core research hypothesis underlying the project is that interpreting small separation phenomena on graphs from the perspective of linear matroids shall be crucial for answering interesting open questions .

Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari and Nicolas Trotignon,
«On the tree-width of even-hole-free graphs«, arXiv (2020).

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos,
«Digraph Coloring and Distance to Acyclicity«, arXiv (2020).

Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum and Daniël Paulusma,
«Tree pivot-minors and linear rank-width«, arXiv (2020).

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomasé, Rémi Watrigan, «Twin-width III: Max Independent Set and Coloring«, arXiv (2020).

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigan, Twin-width II: small classes, In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv.

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation, SODA 2021.

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
Twin-width I: tractable FO model checking, FOCS 2020.

Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos,
A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, ESA 2020.

Chien-Chung Huang, Theophile Thiery and Justin Ward,
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints, APPROX/RANDOM 2020.

Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou and Yota Otachi,
Grundy Distinguishes Treewidth from Pathwidth, ESA 2020.

Jungho Ahn, Eun Jung Kim and Euiwoong Lee,
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion, ISAAC 2020.

The main theme of this project is small separation phenomena on graphs and linear matroids. The concept of separation in theoretical computer science is pervasive, in varying forms depending on the context. Roughly speaking, a small separation of a relational structure, such as graphs and logical formulas,
is a near-(bi)partition of the ground set such that the part of relations that are `crossing' can be described with small bits of information, examples including edge- and vertex-cut, join and many others. Small separation is a fundamental concept that paves the way for graph theory, especially structural decomposition theory. Also it is a major engine for algorithms design.

There are two ways that small separations are acknowledged and deployed in algorithms. First, they could be used to decompose a graph into simple building blocks which are glued along small separations. Structural graph theory is a successful research program that demonstrate the power of such decompositions. Many graph classes are shown to admit such decompositions, which led to numerous efficient algorithms running on decompositions.
In particular, tree-like decompositions based on various notions of separations are a cornerstone of algorithms design. The second arena where small separations are utilized is in charting the solution space through the lens of small separations. Finding a minimum (s,t)-cut is a classic problem for both edge and vertex version, and the problem \textsc{Minimum Cut} and its many variants have been extensively studied till now. There are many fundamental problems that can be termed as `separation problems', for which the solution space can be either directly encoded as a sequence of separations, or can be radically narrowed down using small separations.

For sparse graph families, structural decompositions and their algorithmic consequences are now very well understood. In contrast, when it comes to decompositions based on a dense separation concept, the current knowledge is lagging far behind. Recently, there are fresh evidence that rank-decomposition, the most prominent decomposition based on dense separation, admits simpler and more elegant manoeuvre when it is brought in the realm of linear matroids. For separation problems, there are primary problems
which are long open. Important concepts and techniques witnessed in recent years share duality of packing and covering of paths as a crucial element, albeit often in disguise. Further, the techniques developed for one problem often transfer to another. It is very likely that there is strong resemblance between these problems and a coherent exposition exists. Again, growing evidence point to linear matroids as a doorway.

Our project aims to advance the present-day knowledge on small separation phenomena. The central questions are: For which problems small rankwidth help to obtain efficient algorithms and compressions? Is there a unified framework to explain existing algorithms and compressions for separations problems? Our research hypothesis is that interpreting the small separation phenomena on graphs in terms of linear matroids shall be crucial for answering the above questions. In order to inspect this hypothesis and respond to our central questions, four work programs are suggested. A. Efficient algorithms on linear matroids with small branchwidth. B. Structure of linear matroids with small branchwidth and its applications. C. Combinatorial properties of linear matroid matching and reformulation of existing techniques for separation problems. D. Algorithmic applications of linear matroid matching for separation problems.