Finding an induced subdivision of a digraph

DOI10.1016/J.ENDM.2011.05.003zbMATH Open1268.05191arXiv1309.1553OpenAlexW2884902798MaRDI QIDQ5891097FDOQ5891097

Authors: Frédéric Havet, Jørgen Bang-Jensen, Nicolas Trotignon 

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics, Theoretical Computer Science (Search for Journal in Brave)

Abstract: We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$? The complexity of this problem depends on $D$ and on whether $G$ 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.

Full work available at URL: https://arxiv.org/abs/1309.1553

Recommendations

• Finding a subdivision of a digraph
• Induced subgraphs and path decompositions
• Finding induced subgraphs via minimal triangulations
• scientific article; zbMATH DE number 3898936
• Induced subgraphs of given sizes

zbMATH Keywords

digraphsNP-completeness3-SATinduced paths and cycleslinkings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Cites Work

• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Induced disjoint paths problem in a planar digraph
• Disjoint directed and undirected paths and cycles in digraphs
• The three-in-a-tree problem
• Excluding induced subgraphs
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths

This page was built for publication: Finding an induced subdivision of a digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891097)