Project Outline
The main theme of this project is small separation phenomena on graphs and linear matroids, emphasizing the applications on algorithms design. The concept of separation in theoretical computer science is pervasive, in varying forms depending on the context. It is a fundamental concept that paves the way for graph theory, especially structural decomposition theory. Also it serves as 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 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.
Our project aims to advance the present-day knowledge on small separation phenomena. The expected outcomes upon a successful execution of the project are twofold. First, we provide a novel combinatorial and algorithmic toolkit for graphs of small rank-width and for linear matroids of small branch-width that parallels those developed for graphs of small treewidth. Second, we present a comprehensive framework to disclose the underlying structure of graph separation problems and attain new algorithms, especially for problems where we have been long detained.
Keywords: graph theory, separation, structural decomposition, linear matroids, width parameters of graphs and linear matroids, packing and covering.
Specifics
| ANR JCJC project | ASSK (ANR-18-CE40-0025-01) |
|---|---|
| Full Title | Algorithms with Small Separations acKnowledged: graphs and linear matroids |
| Principal Investigator | Eun Jung Kim |
| Starting Date | 01/01/2019 (54 months) |
| Budget | 211633.56€ |
| Host Institute | LAMSADE (CNRS / University Paris-Dauphine) |