Os tópicos que serão objeto de estudo em torno do Problema 1 revelam a nossa escolha quanto ao que consideramos relevante em termos da proposta de se estudar aspectos estruturais e algorítmicos em grafos. Como já mencionamos, os critérios de seleção foram direcionados pela relevância dos temas, existência de pesquisadores que já trabalham nessa linha e pela possibilidade concreta que o grupo tem de contribuir com resultados que serão de interesse para a comunidade científica internacional que trabalha na área.
A pesquisa relativa aos métodos poliedrais para problemas combinatórios difíceis (cf. Problema 2) será centrada na investigação de alguns problemas que julgamos promissores, usando ferramentas de combinatória poliédrica para estudar a estrutura facial dos poliedros associados a esses problemas. Tal estratégia tem obtido cada vez maior aceitação na comunidade internacional, sendo responsável pelo surgimento de grupos em vários centros do exterior que fazem pesquisa nesta linha (e.g. Berlim, Louvain, Roma). Esta abordagem tem sido considerada especialmente indicada para resolver problemas reais de grande porte. Primeiramente procuraremos obter resultados teóricos relativos aos poliedros associados aos problemas de nosso interesse; uma vez cumprida esta etapa, desenvolveremos e implementaremos algoritmos baseados nesta abordagem. A experiência de alguns dos pesquisadores do grupo no uso desta estratégia (cf. [22, 23, 30, 31, 32, 33]) é uma forte indicação de que alguns resultados relevantes serão obtidos.
Continuando com o Problema 2, observamos que as investigações quanto aos métodos multi-algorítmicos serão baseados na abordagem de Times Assíncronos, já usada com sucesso no problema do Caixeiro Viajante [75], e que serão estendidos para o desenvolvimento de algoritmos para outros problemas combinatórios difíceis, como o problema do roteamento de veículos e o problema do escalonamento de tarefas.
As ferramentas envolvidas nas nossas investigações de métodos probabilísticos aplicados à combinatória e à teoria da computação dentro do Problema 3 incluem, entre outras, várias versões novas do profundo lema de Szemerédi sobre partições de grafos, observadas por nós [45] e outros [2], desigualdades para grandes desvios (martigais, desigualdades de Janson), e expansores. O uso destas ferramentas têm constituído uma técnica frutífera como atestam resultados recentes [11, 12, 13, 14, 15, 35, 36, 37, 38, 39, 46, 47].