Subdivisões de Orientações do Grafo Bipartido Completo K2,3
Resumo
Neste trabalho, exploramos o problema de encontrar uma subdivisão em um digrafo F em um digrafo D, com o objetivo de identificar instâncias Polinomiais e NP-completas do mesmo. Mais especificamente, focamos nos casos em que F é uma orientação do K2,3, na tentativa de ter uma visão mais clara sobre uma conjectura à respeito do problema em grafos planares. Apresentamos todas as possíveis orientações do K2,3 e os casos que o problema pode ser resolvidos de maneira polinomial, utilizando fluxos ou Teorema do Grid Direcionado. A complexidade de apenas um caso permanece em aberto.
Referências
Bang-Jensen, J., Havet, F., and Maia, A. K. (2015). Finding a subdivision of a digraph. Theoretical Computer Science, 562:283 – 303.
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.
Chudnovsky, M. and Seymour, P. (2010). The three-in-a-tree problem. Combinatorica, 30(4):387–417.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. J. Combin. Theory Ser. B, 82(1):138–154.
Kawarabayashi, K.-i. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing.
Lévêque, B., Lin, D. Y., Maffray, F., and Trotignon, N. (2009). Detecting induced subgraphs. Discrete Appl. Math., 157(17):3540–3551.
Robertson, N. and Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65–110.
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.
Chudnovsky, M. and Seymour, P. (2010). The three-in-a-tree problem. Combinatorica, 30(4):387–417.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Granot, D., Granot, F., and Zhu, W. R. (2000). Naturally submodular digraphs and forbidden digraph configurations. Discrete Appl. Math., 100(1-2):67–84.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. J. Combin. Theory Ser. B, 82(1):138–154.
Kawarabayashi, K.-i. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing.
Lévêque, B., Lin, D. Y., Maffray, F., and Trotignon, N. (2009). Detecting induced subgraphs. Discrete Appl. Math., 157(17):3540–3551.
Robertson, N. and Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65–110.
Publicado
20/07/2025
Como Citar
SERRA, Philipe M.; MAIA, Ana Karolinna.
Subdivisões de Orientações do Grafo Bipartido Completo K2,3. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 138-142.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.9473.
