Adapting the directed grid theorem into an FPT algorithm

DOI10.1137/21M1452664MaRDI QIDQ5099098zbMATH OpenOpenAlexWikidataFDO

Authors Victor Campos, Raul Lopes, Ana Karolinna Maia, Ignasi Sau

Publication date 31 August 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.07738

zbMATH Keywords

digraphdirected tree-widthgrid theorem\textsf{FPT} algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12)

Abstract: 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]. Namely, 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 size $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 paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this XP algorithm into an FPT algorithm. Towards this, our main technical contributions are 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$, improving on the original result for arboreal decompositions by Johnson et al. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. 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|$, a result that we consider to be of its own interest.

Recommendations

• The directed grid theorem
• An excluded grid theorem for digraphs with forbidden minors
• Towards the graph minor theorems for directed graphs
• Polynomial planar directed grid theorem
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

Cites work

• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• scientific article; zbMATH DE number 6820196 (Why is no real title available?)
• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• A fixed-parameter algorithm for the directed feedback vertex set problem
• An algorithmic metatheorem for directed treewidth
• An excluded grid theorem for digraphs with forbidden minors
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Classes of directed graphs
• Complexity of Finding Embeddings in a k-Tree
• Digraph decompositions and monotonicity in digraph searching
• Digraph width measures in parameterized algorithmics
• Directed tree-width
• Encyclopedia of algorithms. In 3 volumes
• Exponential polynomials
• Finding detours is fixed-parameter tractable
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fundamentals of parameterized complexity
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph searching and a min-max theorem for tree-width
• Graph theory
• Half-integral linkages in highly connected directed graphs
• Multicut Is FPT
• Nonserial dynamic programming
• On directed feedback vertex set parameterized by treewidth
• Parameterized algorithms
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parametrized complexity theory.
• Polynomial bounds for the grid-minor theorem
• Polynomial planar directed grid theorem
• Quantitative graph theory. Mathematical foundations and applications
• S-functions for graphs
• Solving frequency assignment problems via tree-decomposition
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• The Directed Flat Wall Theorem
• The directed grid theorem
• The directed subgraph homeomorphism problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tour merging via branch-decomposition
• Towards a polynomial kernel for directed feedback vertex set
• Towards tight(er) bounds for the excluded grid theorem
• Treewidth: Characterizations, Applications, and Computations

Cited in

(5)

• Excluding a planar matching minor in bipartite graphs
• Adapting the directed grid theorem into an \textsf{FPT} algorithm
• The directed grid theorem
• Towards the graph minor theorems for directed graphs
• An excluded grid theorem for digraphs with forbidden minors

This page was built for publication: Adapting the directed grid theorem into an FPT algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5099098)