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.