We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Induced disjoint paths in AT-free graphs

Golovach, P.A. and Paulusma, D. and van Leeuwen, E.J. (2022) 'Induced disjoint paths in AT-free graphs.', Journal of computer and system sciences., 124 . pp. 170-191.


Paths P1, . . . , Pk in a graph G = (V, E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si, ti) contains k mutually induced paths Pi such that each Pi connects si and ti. This is a classical graph problem that is NP-complete even for k = 2. We study it for AT-free graphs. Unlike its subclasses of permutation graphs and cocomparability graphs, the class of AT-free graphs has no known characterisation by a geometric intersection model. However, by a new, structural analysis of the behaviour of Induced Disjoint Paths for AT-free graphs, we prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. This is in contrast to the situation for other well-known graph classes, such as planar graphs, claw-free graphs, or more recently, (theta,wheel)-free graphs (JCTB 2021), for which such a result only holds if k is fixed. As a consequence of our main result, the problem of deciding if a given ATfree graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. In addition, we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter |VH|, even on a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-in-a-Path and k-in-a-Tree are polynomialtime solvable on AT-free graphs even if k is part of the input. These problems are to test if a graph has an induced path or induced tree, respectively, spanning k given vertices.

Item Type:Article
Full text:Publisher-imposed embargo until 29 October 2022.
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF
Publisher Web site:
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:18 October 2021
Date deposited:25 October 2021
Date of first online publication:29 October 2021
Date first made open access:29 October 2022

Save or Share this output

Look up in GoogleScholar