Golovach, P.A. and Paulusma, Daniel and van Leeuwen, E.J. (2012) 'Induced disjoint paths in AT-free graphs.', in *Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings.* Berlin ; Heidelberg: Springer, pp. 153-164. Lecture notes in computer science. (7357).

## Abstract

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti for i = 1,…,k. This problem is known to be NP-complete already for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. As a consequence, the problem of testing whether a given AT-free graph contains some graph H as an induced topological minor admits a polynomial-time algorithm, as long as H is fixed; we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard, even on a subclass of AT-free graphs, namely cobipartite graphs, when parameterized by |VH|. We also show that the problems k-in-a-Path and k-in-a-Tree can be solved in polynomial time, even when k is part of the input. These problems are to test whether a graph contains an induced path or induced tree, respectively, spanning k given vertices.

Item Type: | Book chapter |
---|---|

Full text: | Full text not available from this repository. |

Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-31155-0_14 |

Date accepted: | No date available |

Date deposited: | No date available |

Date of first online publication: | 2012 |

Date first made open access: | No date available |

## Save or Share this output

Export: | |

Look up in GoogleScholar |