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:||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|