Home | About | Research | Publications | Trips | Personal | Contact

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_H contains H as an induced immersion.