Descrição do problema

Problema: Dado um grafo com arestas de comprimento $1$ ou $-1$ determinar um circuito de comprimento negativo, ou um certificado de sua inexistência. O comprimento de um circuito é a soma dos comprimentos de suas arestas. O certificado que garante a inexistência de circuitos negativos será explicado posteriormente.

Esse problema é essencialmente equivalente ao da determinação de uma $T$-junção mínima (minimum T-join) em um grafo sem comprimentos.

András Sebo [6] (e, independentemente, C. Lucchesi [1]) criou um algoritmo polinomial para resolver o problema. O algoritmo é um tanto complexo e sua implementação eficiente apresenta interessantes desafios e dificuldades.

O presente projeto pretende implementar e testar o algoritmo de Sebo. A implementação usará o Stanford GraphBase de D. E. Knuth [3].