Raul Lopes gave an online talk on the FPT algorithm for finding the cylindrical grid in a directed graph of large directed tree-width at the Virtual Discrete Math Colloquium

On May 6, 2021, Raul Lopes from Universidade Federal do Ceará gave an online talk at the Virtual Discrete Math Colloquium providing a fixed-parameter tractable algorithm to find a large cylindrical grid as a butterfly minor in a directed graph of large directed tree-width. The title of his talk was “Adapting the Directed Grid Theorem into an FPT Algorithm“.

Raul Lopes, Adapting the Directed Grid Theorem into an FPT Algorithm

The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001] , and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor.

In this talk, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|.

Joint work with Victor Campos, Ana Karolinna Maia, and Ignasi Sau.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.