Susanna Figueiredo de Rezende
Supervisora: Profa. Dra. Yoshiko Wakabayashi
6 de junho de 2011
Em teoria dos grafos, problemas sobre caminhos são uns dos mais fundamentais. Dentre estes, destaca-se o problema da existência e busca de caminhos de certos comprimentos. Nesse trabalho daremos enfoque a problemas sobre caminhos mais longos em grafos. Consideraremos basicamente duas classes de problemas: os de natureza algorítmica e os de natureza estrutural.
Na primeira parte, investigaremos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários [6]. Porém, para algumas classes específicas de grafos existem algoritmos polinomiais para encontrar um caminho mais longo. Nesse trabalho estudaremos algumas dessas classes e os respectivos algoritmos.
Na segunda parte, apresentaremos uma resenha sobre problemas de enfoque mais estrutural relativos à intersecção de caminhos mais longos em um grafo. Mais precisamente, investigaremos problemas motivados pela seguinte questão levantada por Gallai [5] em 1966: é verdade que em um grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Sabe-se que a resposta a essa questão é negativa. Há, porém, algumas classes de grafos para as quais a resposta é positiva.
Estudaremos o caso em que se considera a intersecção de todos os caminhos mais longos, e também o caso em que se considera apenas um número fixo de caminhos mais longos. Investigaremos essas questões em grafos arbitrários, e também em certas classes especiais de grafos. Mencionaremos alguns resultados conhecidos, e apresentaremos a prova de alguns deles. Além da resenha, apresentaremos alguns resultados que obtivemos recentemente sobre este tópico.
O objetivo desse trabalho é o estudo aprofundado de alguns tópicos específicos da teoria dos grafos. Estudaremos problemas sobre caminhos mais longos em grafos, enfocando tanto problemas de natureza algorítmica como de natureza estrutural. Acreditamos que é bastante interessante estudar assuntos correlatos sob enfoques diferentes. Desenvolver algoritmos para encontrar caminhos mais longos pode ajudar a entender melhor a questão da existência de vértices comuns a todos os caminhos mais longos; ou provar a existência de algum objeto tanto pode ser um resultado estrutural ou de cunho mais algorítmico. Assim, tendo como tema central o estudo de caminhos mais longos em grafos, estudaremos os resultados conhecidos, e também procuraremos descobrir novos resultados. Esta monografia conterá uma resenha dos resultados conhecidos e também os resultados originais que já obtivemos e outros que esperamos obter.
Em 2010, como atividade de IC, estudei um artigo de M. Axenovich [1], sobre intersecção de três caminhos mais longos em um grafo exoplanar. Logo depois, tive a oportunidade de apresentar um seminário sobre esse artigo.
A leitura desse artigo motivou-nos a aprofundar os nossos estudos sobre esse tema e outros correlatos. Ao longo do ano passado estudamos a história e os resultados conhecidos sobre problemas a respeito de intersecção de caminhos mais longos em grafos.
Elaboramos uma monografia baseada nesse estudo para o V Simpósio Nacional / Jornadas de Iniciação Científica organizado pelo IMPA em 2010. Nesse trabalho apresentamos uma resenha sobre problemas de enfoque mais estrutural. Mais precisamente, investigamos algumas variações da questão levantada por Gallai [5] em 1966 sobre a existência de um vértice comum a todos os caminhos mais longos de um grafo conexo. O resultado principal dessa monografia é a prova de que num grafo exoplanar conexo existe um vértice comum a todos os seus caminhos mais longos. Este resultado, além de ser mais simples, generaliza o resultado de Axenovich [1] que garante que num grafo exoplanar conexo existe um vértice comum a quaisquer três caminhos mais longos.
Esta monografia foi selecionada para apresentação oral nesse simpósio, e foi também premiada com medalha de ouro (veja mais informações aqui).
Pretendemos elaborar um artigo completo com o resultado principal da monografia, e alguns novos que obtivemos recentemente, relacionados ao tema. Por ora, temos um resumo estendido (que estará disponível em breve) que foi aceito no EuroComb 2011 (European Conference on Combinatorics).
junho/julho - estudo de questões estruturais
agosto/setembro - estudo de questões algorítmicas
outubro/novembro - preparação do pôster e da apresentação
julho/outubro - elaboração da monografia
novembro - revisão da monografia
A monografia será composta por duas partes: a parte técnica e a parte subjetiva.
A parte técnica conterá os seguinte tópicos:
A parte subjetiva conterá os seguintes tópicos:
Listamos a seguir os artigos relacionados ao tema de nossa
monografia. Alguns deles já foram estudados, outros ainda serão
estudados, dependendo do andamento da pesquisa. Os livros constituem
o material básico de nossos estudos: são fontes de consulta e, além
disso, vários de seus capítulos foram ou ainda serão estudados.
[1] Axenovich, M., When do three longest paths have a common vertex?, Discrete Mathematics, Algorithms and Applications 1 (2009), pp. 115-120
[2] Balister, P., E. Győri, J. Lehel and R. Schelp, Longest paths in circular arc
graphs, Combin. Probab. Comput. 13 (2004), pp. 311-317.
[3] Bondy, J.A. and U.S.R. Murty, Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.
[4] Bulterman, R.W., F.W. van der Sommen, G. Zwaan, T. Verhoe, A.J.M. van Gasteren,
and W.H.J. Feijen, On computing a longest path in a tree. Inform. Process. Lett.,
81(2):93-96, 2002.
[5] Gallai, T., Problem 4, in: Theory of Graphs (1968), p. 362.
[6] Garey, M.R. and D.S. Johnson, Computers and intractability. W. H. Freeman and Co.,
San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of
Books in the Mathematical Sciences.
[7] Grünbaum, B, Vertices missed by longest paths or circuits. J. Combinatorial Theory
Ser. A, 17:31-38, 1974.
[8] Hatzel, W., Ein planarer hypohamiltonscher Graph mit 57 Knoten. Math. Ann.,
243(3):213-216, 1979.
[9] Ioannidou, K., G. Mertzios, and S. Nikolopoulos, The longest path problem is polynomial on interval graphs.
In Rastislav Královic and Damian Niwinski, editors, Mathematical Foundations of Computer Science 2009,
volume 5734 of Lecture Notes in Computer Science, pages 403-414. Springer Berlin / Heidelberg, 2009.
[10] Ioannidou, K. and S. Nikolopoulos, The longest path problem is polynomial on cocomparability graphs. In
Dimitrios Thilikos, editor, Graph Theoretic Concepts in Computer Science, volume 6410 of Lecture Notes in
Computer Science, pages 27-38. Springer Berlin / Heidelberg, 2010.
[11] Klavžar, S. and M. Petkovšek, Graphs with non empty intersection of longest
paths, Ars Combin. 29 (1990), pp. 13-52.
[12] Pelikán J., L. Lovász and K. Vesztergombi, Discrete Mathematics: elementary and beyond. Undergraduate
Texts in Mathematics. Springer-Verlag, New York, 2003.
[13] Research problems, Discrete Mathematics 167/168 (1997), pp. 605-615, 15th
British Combinatorial Conference.
[14] Schmitz, W., Über längste Wege und Kreise in Graphen. Rend. Sem. Mat. Univ. Padova,
53:97-103, 1975.
[15] Skupień, Z., Smallest sets of longest paths with empty intersection, Combin.
Probab. Comput. 5 (1996), pp. 429-436.
[16] Takamizawa, K., T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on seriesparallel
graphs. J. ACM, 29:623-641, July 1982.
[17] Uehara, R. and Y. Uno, Efficient algorithms for the longest path problem. In Rudolf Fleischer and Gerhard
Trippen, editors, Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages
1547-1553. Springer Berlin / Heidelberg, 2005.
[18] Uehara, R. and Y. Uno, On computing longest paths in small graph classes. Internat.
J. Found. Comput. Sci., 18(5):911-930, 2007.
[19] Walther, H., Über die Nichtexistenz eines Knotenpunktes, durch den alle
längsten Wege eines Graphen gehen, J. Combinatorial Theory 6 (1969), pp. 1-6.
[20] Walther, H. and H.-J. Voss, Über Kreise in Graphen, VEB Deutscher Verlag
der Wissenschaften (1974).
[21] Zamfirescu, T., A two-connected planar graph without concurrent longest paths. J.
Combinatorial Theory, 13:116-121, 1972.
[22] Zamfirescu, T., On longest paths and circuits in graphs, Math. Scand. 38 (1976),
pp. 211-239.
[23] Zamfirescu, T., Intersecting longest paths or cycles: a short survey, An. Univ.
Craiova Ser. Mat. Inform. 28 (2001), pp. 1-9.