Publication at Faculty of Mathematics and Physics |
2012
Abstract
The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge con- tractions. When H is fixed, i.e., not part of the input, this problem is denoted H-Induced Minor.
We provide polynomial-time algorithms for this problem in the case that the fixed target graph has a star-like structure. In particular, we show polynomial-time solvability for all forests H on at most seven vertices except for one such case.