Adapting the directed grid theorem into an FPT algorithm

DOI10.1137/21M1452664zbMATH Open1496.05059arXiv2007.07738OpenAlexW3043413734WikidataQ113779006 ScholiaQ113779006MaRDI QIDQ5099098FDOQ5099098

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)

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.

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

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

zbMATH Keywords

digraphdirected tree-widthgrid theorem\textsf{FPT} algorithm

Mathematics Subject Classification ID

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

Cites Work

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

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)