Finding an induced subdivision of a digraph

详细信息	查看全文 | 推荐本文 |

• 作者：Jø ; rgen Bang-Jensen^a ; ^{jbj@imada.sdu.dk} ; Fré ; dé ; ric Havet^b ; ^{Frederic.Havet@inria.fr} ; ^{Frederic.Havet@sophia.inria.fr} ; Nicolas Trotignon^c ; ^{nicolas.trotignon@ens-lyon.fr}
• 关键词：NP-completeness ; Induced paths and cycles ; Linkings ; 3-SAT
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：20 July, 2012
• 卷：443
• 期：Complete
• 页码：10-24
• 文件大小：370 K

摘要

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.