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: