id: 05988635 dt: a an: 05988635 au: Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar; van ’t Hof, Pim; Kamiński, Marcin; Paulusma, Daniël ti: Finding contractions and induced minors in chordal graphs via disjoint paths. so: Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5‒8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 110-119 (2011). py: 2011 pu: Berlin: Springer la: EN cc: ut: ci: li: doi:10.1007/978-3-642-25591-5_13 ab: Summary: 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,\cdots ,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,\cdots ,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. rv: