## Induced immersions

*Rémy Belmonte, Pim van 't Hof and Marcin Kamiński*

This paper appeared in the proceedings of ISAAC 2012, the 23rd International Symposium on Algorithms and Computation (held on December 19-21, 2012 in Taipei, Taiwan), *Lecture Notes in Computer Science*, vol. 7676, pp. 299-308, 2012.

[__DOI__]

### Abstract:

A graph *G* contains a multigraph *H* as an induced immersion if *H* can be obtained from *G* by a sequence of vertex deletions and lifts. We present a polynomial-time algorithm that decides for any fixed multigraph *H* whether an input graph *G* contains *H* as an induced immersion. We also show that for every multigraph *H* with maximum degree at most 2, there exists a constant *c _{H}* such that every graph with treewidth more than

*c*contains

_{H}*H*as an induced immersion.