Skip to Main content Skip to Navigation
Journal articles

Adapting The Directed Grid Theorem into an FPT Algorithm

Victor Campos 1 Raul Lopes 1 Ana Karolinna Maia 1 Ignasi Sau Valls 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Originally proved in 1986 by Robertson and Seymour, the Grid Theorem 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 isn directed graphs was conjectured by Johnson et al. in 2001, and proved recently by Kawarabayashi and Kreutzer in 2015. Namely, they showed that there is a function f(k) such that every directed graph of directed tree-width at least f(k) contains a cylindrical grid of size k as a butterfly minor. Moreover, they claim 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 article, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer and we improve the XP algorithm into an FPT algorithm. The first step of the proof is an XP algorithm by Johnson et al. in 2001 that decides whether a directed graph D has directed tree-width at most 3k − 2 or admits a haven of order k. It is worth mentioning that a skecth of an FPT algorithm for this problem appears in Chapter 9 of the book ”Classes of Directed Graphs”, from 2018, with an approximation factor of 5k + 2. Our first contribution is to adapt the proof from Johnson et al. to find either an arboreal decomposition of width at most 3k − 2 or a haven of order k in a directed graph D in FPT time, by making use of important separators. We then follow the roadmap of the proof by Kawarabayashi and Kreutzer by locally improving the complexity at some steps, in particular concerning the problem of finding hitting sets for brambles of large order.
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410620
Contributor : Ignasi Sau <>
Submitted on : Friday, December 13, 2019 - 10:07:53 PM
Last modification on : Wednesday, June 24, 2020 - 10:48:04 AM

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

Victor Campos, Raul Lopes, Ana Karolinna Maia, Ignasi Sau Valls. Adapting The Directed Grid Theorem into an FPT Algorithm. Electronic Notes in Theoretical Computer Science, Elsevier, 2019, 346, pp.229-240. ⟨10.1016/j.entcs.2019.08.021⟩. ⟨lirmm-02410620⟩

Share

Metrics

Record views

187

Files downloads

484