Detecting induced star-like minors in polynomial time

Abstrakt

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.

Klíčová slova

• Induced minor
• tree
• computational complexity