Aspectos Algorítmicos de Imersões em Digrafos
Resumo
Imersão, forte ou fraca, é uma importante relação de contenção entre (di)grafos. Determinar se um digrafo H está imerso em um digrafo G é um problema NP-completo no caso geral. Neste artigo, propomos algoritmos polinomiais para duas classes específicas de digrafos e provamos a NP-completude do teste de imersão de H quando este satisfaz certas condições.Referências
Bang-Jensen, J. and Gutin, G. Z. (2008). Digraphs: Theory, Algorithms and Applications. Springer Publishing Company, Incorporated, 2nd edition.
Bondy, J. and Murty, U. (2008). Graph Theory. Springer Publishing Company, Incorporated, 1st edition.
Chudnovsky, M., Fradkin, A., and Seymour, P. (2012). Tournament immersion and cutwidth. Journal of Combinatorial Theory, Series B, 102(1):93–101.
Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Ann. of Math. (2), 164(1):51–229.
Chudnovsky, M. and Seymour, P. (2007). Excluding induced subgraphs. In Surveys in combinatorics 2007, volume 346 of London Math. Soc. Lecture Note Ser., pages 99–119. Cambridge Univ. Press, Cambridge.
DeVos, M., McDonald, J., Mohar, B., and Scheide, D. (2012). Immersing complete digraphs. European Journal of Combinatorics, 33(6):1294–1302.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Kim, I. (2013). On containment relations in directed graphs. PhD thesis, Princeton University.
Kim, I. and Seymour, P. (2013). On Containment Relations on Digraphs. PhD thesis, Princeton, NJ : Princeton University.
Lochet, W. (2019). Immersion of transitive tournaments in digraphs with large minimum outdegree. Journal of Combinatorial Theory, Series B, 134:350–353.
Robertson, N. and Seymour, P. D. (1995). Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110.
Bondy, J. and Murty, U. (2008). Graph Theory. Springer Publishing Company, Incorporated, 1st edition.
Chudnovsky, M., Fradkin, A., and Seymour, P. (2012). Tournament immersion and cutwidth. Journal of Combinatorial Theory, Series B, 102(1):93–101.
Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Ann. of Math. (2), 164(1):51–229.
Chudnovsky, M. and Seymour, P. (2007). Excluding induced subgraphs. In Surveys in combinatorics 2007, volume 346 of London Math. Soc. Lecture Note Ser., pages 99–119. Cambridge Univ. Press, Cambridge.
DeVos, M., McDonald, J., Mohar, B., and Scheide, D. (2012). Immersing complete digraphs. European Journal of Combinatorics, 33(6):1294–1302.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Kim, I. (2013). On containment relations in directed graphs. PhD thesis, Princeton University.
Kim, I. and Seymour, P. (2013). On Containment Relations on Digraphs. PhD thesis, Princeton, NJ : Princeton University.
Lochet, W. (2019). Immersion of transitive tournaments in digraphs with large minimum outdegree. Journal of Combinatorial Theory, Series B, 134:350–353.
Robertson, N. and Seymour, P. D. (1995). Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110.
Publicado
19/07/2026
Como Citar
BEZERRA, Luís A. L.; COSTA, Jonas; MAIA, Ana K..
Aspectos Algorítmicos de Imersões em Digrafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 51-55.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.23693.
