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:

Finding contractions and induced minors in chordal graphs via disjoint paths.

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).


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:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:2011
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar