Finding an induced subdivision of a digraph
arXiv:1309.1553 · doi:10.1016/j.tcs.2012.03.017
Abstract
We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) , does it contain an induced subdivision of a prescribed digraph ? The complexity of this problem depends on and on whether must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.