A lower bound for the tree-width of planar graphs with vital linkages

2010/11/09 by Isolde Adler, Adler, Isolde, Philipp Klaus Krause +1
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.1011.2136

9 pages, 9 figures

arxiv created 2010/11/09 · arxiv updated 2010/11/10

Abstract

The disjoint paths problem asks, given an graph G and k + 1 pairs of terminals (s₀,t₀), ...,(s_k,t_k), whether there are k+1 pairwise disjoint paths P₀, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour have proven that the problem can be solved in polynomial time if k is fixed. Nevertheless, the constants involved are huge, and the algorithm is far from implementable. The algorithm uses a bound on the tree-width of graphs with vital linkages, and deletion of irrelevant vertices. We give single exponential lower bounds both for the tree-width of planar graphs with vital linkages, and for the size of the grid necessary for finding irrelevant vertices.

Related

• Irrelevant Vertices for the Planar Disjoint Paths Problem
• Optimal Bounds for the k-Disjoint Paths Problem
• Planar Disjoint Paths, Treewidth, and Kernels
• An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs