Começamos tecendo algumas considerações relativas ao Problema 1, Investigações de problemas estruturais e algorítmicos em grafos. Dentro da área de Combinatória a Teoria dos Grafos tem um papel de grande destaque, tanto pelo seu aspecto puramente teórico como pela sua aplicabilidade nas mais diversas áreas como Ciência da Computação, Química Orgânica, Biologia Computacional, Mecânica Quântica, Economia, etc.
No que diz respeito aos fundamentos da Teoria dos Grafos, os problemas ligados ao reconhecimento de estruturas presentes em certas classes de grafos têm sido largamente investigados e têm trazido grandes contribuições tanto a nível teórico quanto prático, fornecendo subsídios para o desenvolvimento de algoritmos eficientes para vários problemas relativos a tais estruturas.
Neste contexto, alguns dos tópicos que serão objeto de estudo são: emparelhamentos, circuitos e caminhos, cortes e tranversais, coloração de grafos e grafos perfeitos.
Vale aqui destacar que problemas relativos a emparelhamentos, circuitos (induzidos ou não) e caminhos com ou sem restrição quanto à paridade de seus comprimentos, são problemas clássicos que têm sido objeto de estudo constante nas duas últimas décadas, ocupando ainda hoje posição de destaque dentro da área (cf. [6, 53, 60]). Isto justifica a inclusão de tais estudos no presente projeto, mormente dada a participação de pesquisadores deste grupo que já vêm contribuindo com resultados relevantes sobre esses tópicos (Benatti, Hashimoto, e Wakabayashi [10], Kohayakawa [44], Lauer e Szwarcfiter [49], Porto [63], Setubal [70]).
Quanto ao estudo de colorações em grafos, a atividade de pesquisa nas equações de Birkhoff-Lewis, propostas em 1945, estiveram dormentes por longo tempo, de 1948 a 1988, com alguma atividade em meados da década de 70. Em 1988, W.T. Tutte reformulou as equações de Birkhoff e Lewis, simplificando-as grandemente, possibilitando avanços em 1991 pelo próprio Tutte e abrindo as portas para a solução dada em Dahab [17]. A natureza dos resultados de Tutte e em [17] apontam para uma conexão ainda não explorada com áreas da Matemática e Física, apontadas no Item 10 deste Volume, e que despertam hoje grande interesse na comunidade científica.
Assim como no caso dos tópicos acima, pesquisas sobre grafos de intersecção, grafos clique, grafos perfeitos e grafos Helly também justificam-se de forma análoga. Destacaremos aqui apenas a classe dos grafos perfeitos, que passou a ser estudada no início dos anos 60, e que tem sido responsável por uma vasta literatura a respeito. Uma das conjecturas mais célebres na Teoria dos Grafos é a Conjectura Forte dos Grafos Perfeitos, proposta por Claude Berge há 30 anos, e que até hoje encontra-se em aberto. Ademais, uma das instituições participantes deste projeto, a UFRJ, sob a liderança de Jayme Szwarcfiter, tem-se projetado a nível internacional, formando pesquisadores na área e contribuindo com resultados de interesse para a comunidade (cf. por exemplo Figueiredo [24, 25], e Porto [63]).
Mais recentemente, o grupo da UFRJ, em colaboração com pesquisadores da UNICAMP, tem desenvolvido pesquisa sobre uma classe especial de grafos perfeitos, os grafos de intervalo, que têm um papel importante em Biologia Computacional, notadamente em problemas sobre seqüenciamento de DNA (cf. Meidanis [58]).
Considerando o acima exposto, é natural o interesse do grupo no Problema 1, dada a relevância dos tópicos envolvidos dentro da combinatória e a presença de pesquisadores no grupo que já vêm atuando nessa linha.
Quanto ao Problema 2, Estudo de métodos poliedrais e multi-algorítmicos para problemas combinatórios NP -difíceis, vale aqui ressaltar os seguintes pontos.
A área de Otimização Combinatória tem recebido um grande impulso nas duas últimas décadas, pela sua importância no tratamento de problemas de caráter combinatório que surgem em áreas tão diversas como classificação de dados, projetos de circuitos VLSI, roteamento de veículos, escalonamento de tarefas a serem executadas em várias máquinas, etc.
Para resolver problemas desta área, quase sempre NP -difíceis, vários métodos exatos e heurísticos têm sido desenvolvidos. Dentre os problemas difíceis de otimização combinatória que têm merecido um estudo mais intensivo, o mais conhecido é sem dúvida o Problema do Caixeiro Viajante. Esse problema tem desafiado pesquisadores da área por mais de 30 anos. Entre as estratégias de maior sucesso na solução exata de instâncias de grande porte para esse problema encontram-se aqueles baseados em métodos poliedrais (Padberg e Grötschel [61], Padberg e Rinaldi [62], Applegate, Bixby, Cook, e Chvátal [5]).
Esses métodos mostraram-se adequados também quando aplicados a outros problemas difíceis de otimização combinatória, tais como o Problema do Corte Máximo (Barahona e Mahjoub [8]), o Problema da Ordem Linear (Grötschel, Jünger e Reinelt [27]), o Problema da Partição em Cliques (Grötschel e Wakabayashi [30]), o Problema da Pré-ordem Completa (Gurgel e Wakabayashi [33, 34]), o Problema das Mochilas Múltiplas (Ferreira, Martin e Weismantel [22, 23]) e o Problema de Empacotamento de Árvores de Steiner (Martin [57]). Este fato justifica a inclusão do estudo desses métodos no presente projeto.
Ainda que a abordagem poliédrica tenha produzido muitos resultados positivos, para muitos problemas, o tamanho das instâncias que podem ser resolvidas com tal abordagem ainda é muito pequeno se comparado com o tamanho das instâncias que se deseja resolver na prática. Assim, o desenvolvimento de outras heurísticas eficientes que produzam soluções satisfatórias é fundamental. Considerando porém que métodos heurísticos podem ter comportamentos totalmente distintos, dependendo da instância dos problemas a que o algoritmo é aplicado, uma abordagem alternativa seria a de se ter vários algoritmos heurísticos (resfriamento termodinâmico, busca tabu) para resolver um certo problema, cabendo a um algoritmo `principal' optar por um dos algoritmos, caso um método exato não esteja disponível ou demande um tempo de execução demasiadamante longo. Esta escolha nao é óbvia, pois não se conhece uma técnica que possa indicar qual algoritmo propiciará a melhor solução para uma instância especifíca de um certo problema. Põe-se então o problema: como tirar proveito de um conjunto de algoritmos que têm características distintas uns dos outros, de forma que se ajudem reciprocamente?
Uma solução para esta questão foi proposta por Pedro Sérgio de Souza em sua tese de doutorado [75], onde o autor faz uso de um conjunto de algoritmos heurísticos para resolver o Problema do Caixeiro Viajante. A técnica usada então foi chamada de Time Assíncrono (Asynchronous Teams). Souza mostrou que a utilização dessa técnica é muito adequada para o Problema do Caixeiro Viajante e fez conjecturas que tal técnica também deve ser adequada para outros problemas combinatórios.
Além dessas estratégias, cabe aqui citar outros tipos de enfoque que têm sido usados na solução dos chamados Problemas de Empacotamento, que dentro dessa área têm um papel de destaque, devido a suas diversas aplicações [50, 51, 68] e pela existência de algoritmos polinomiais com bons limites de desempenho assintótico para se resolvê-los.
No que diz respeito ao Problema 3, Investigações de aplicações de métodos probabilísticos em combinatória e em teoria da computação, começamos notando aqui que o resfriamento termodinâmico mencionado acima é um método que é fundamentalmente probabilístico. É de fato o caráter probabilístico de certos procedimentos algorítmicos um dos tópicos em que nos concentraremos dentro destre projeto. O poder da introdução de elementos aleatórios em procedimentos algorítmicos é muito bem ilustrado pelo recente sucesso, no ataque de vários problemas importantes, das técnicas baseadas em passeios aleatórios rapidly mixing--método este intrinsicamente probabilístico. Destacamos aqui os algoritmos eficientes de cálculo de volume de corpos convexos dados por oráculos (cf. Dyer e Frieze [18] e Lovász e Simonovits [52]). Cabe salientar que foi provada a não existência de versões determinísticas de tais algoritmos.
Outro contexto em que procedimentos probabilísticos são fundamentais é aquele de verificações aleatórias (``randomized checking''). De fato, é dentro deste contexto que os resultados recentes de verificação de provas e aproximabilidade foram obtidos. Estas investigações culminaram com o trabalho de Arora, Lund, Motwani, Sudan, e Szegedy [7], que estabeleceu uma caracterização surpreendente da classe NP . O impacto deste resultado foi profundo na comunidade de cientistas teóricos da computação, e esta descoberta até chegou a ser anunciada no New York Times.
Dada a evolução da teoria da computação nesta direção claramente probabilística, hoje é imprescindível que os pesquisadores que trabalham nesta área tenham uma grande familiaridade com métodos probabilísticos. Isto justifica o nosso interesse em concentrarmos os nossos esforços na investigação de técnicas probabilísticas na teoria da computação, notadamente nos contextos acima citados.
Mais especificamente, além da busca de algoritmos probabilísticos específicos para problemas concretos e do estudo de aspectos teóricos da existência ou não de tais algoritmos, planejamos investigar certos problemas de caráter fundamental em combinatória tanto pelo seu interesse intrínseco como pela aplicabilidade à teoria da computação das técnicas desenvolvidas neste processo. Destacamos três linhas de pesquisa em que nossas investigações têm-se concentrado e que serão importantes dentro deste projeto.
Grafos aleatórios. As estruturas combinatórias
aleatórias melhor entendidas atualmente são os grafos aleatórios. Esta
teoria foi fundada por Erdos e Rényi no começo da década de 60, e
o nível de sofisticação dos resultados e das técnicas atuais são
impressionantes. Veja, por exemplo, Janson, 
uczak, Knuth, e
Pittel [40]. Dentro deste assunto, temos efetuado um estudo
sistemático dos subgrafos aleatórios do hipercubo
n-dimensional [11, 12, 13, 14]. Além do interesse
intrínseco, lembrando que o hipercubo é uma arquitetura importante
para máquinas paralelas, o nosso estudo poderá no futuro ser relevante
em investigações sobre paralelismo.
Problemas em teoria de Ramsey.
Em [15, 35, 36, 37, 46, 47]
investigamos vários problemas determinísticos dentro da teoria de
Ramsey por meio de técnicas probabilísticas. A teoria de Ramsey é uma
área de grande interesse em combinatória, e o uso cada vez maior de
técnicas probabilísticas nesta área é certo. Mencionamos aqui que um
resultado profundo recentemente provado por Rödl e
Rucinski [65, 66], referente a propriedades de Ramsey do grafo
aleatório binomial 
, abre novas e promissoras possibilidades de
interação entre os métodos probabilísticos e a teoria de Ramsey.
Problemas extremais em grafos aleatórios. Seguindo os trabalhos de Rödl e Rucinski [65, 66], investigamos recentemente o problema extremal tipo Turán em grafos aleatórios, obtendo resultados completos quando o circuito de um dado comprimento é o grafo proibido [38, 39]. Ainda há muito mais nesta direção a ser estudado.
Versões determinísticas de algoritmos aleatórios. Métodos probabilísticos tipicamente fornecem algoritmos aleatórios para solucionar os problemas considerados, mas técnicas engenhosas têm sido desenvolvidas para se transformar alguns destes algoritmos em algoritmos determinísticos polinomiais [1, 3, 9]. Planejamos investigar estas técnicas recentes para aplicá-las em problemas algorítmicos de nosso interesse.