Belmonte, R. and Golovach, P.A. and Heggernes, P. and Hof van 't, P. and Kaminski, M. and Paulusma, Daniel (2011) 'Finding contractions and induced minors in chordal graphs via disjoint paths.', in *Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings.* Berlin: Springer, pp. 110-119. Lecture notes in computer science. (7074).

## Abstract

The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of this problem, where the vertices of P i must belong to a specified vertex subset U i for i = 1,…,k. In contrast to the original problem, which is polynomial-time solvable for any fixed integer k, we show that this variant is NP-complete even for k = 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer k if the input graph is chordal. We use this result to show that, for any fixed graph H, the problems H-Contractibility and H-Induced Minor can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph G contains H as a contraction or as an induced minor, respectively.

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-25591-5_13 |

Record Created: | 13 Dec 2011 12:05 |

Last Modified: | 03 Apr 2013 16:24 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |