2019/01/14 by Isolde Adler, Philipp Klaus Krause · 1 citation
Computer Science · Mathematics · #cs.DM #math.CO
paper · pdf · doi:10.1016/j.jctb.2018.12.008
arxiv created 2019/01/14 · arxiv updated 2019/01/15
For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there is a function f such that if the tree-width of a graph G with k pairs of terminals is at least f(k), then G contains a solution-irrelevant vertex (Graph Minors. XXII., JCTB 2012). We give a single-exponential lower bound on f. This bound even holds for planar graphs.