Being even slightly shallow makes life hard

Irene Muzi, Michael P. O'Brien, Felix Reidl +1

We study the computational complexity of identifying dense substructures, namely $r/2$-shallow topological minors and $r$-subdivisions. Of particular interest is the case when $r=1…