Algoritmos aproximativos [LAB-1]

Problema: Subgrafo de maior densidade¶

** esta atividade apresenta um problema novo não visto em sala de aula

Densidade de um grafo: uma possível definição para densidade de um grafo é a razão entre a sua quantidade de arestas em relação à sua quantidade de vértices. Portanto, seja um grafo $G(V,E)$, sua densidade $r(G)$ é dada por:

$r(G) = \frac{|E|}{|V|}$

Subgrafo de um grafo (subgrafo induzido): um subgrafo $S \subseteq V$ de um grafo $G(V,E)$ é um subconjunto de vértices juntamente com as arestas $E_S \subseteq E$ que envolvem apenas vértices desse subconjunto. Portanto, em termos de densidade para o subgrafo, temos que:

$r(S) = \frac{|{(u,v) \in E ~\mid~ u,v \in S}|}{|S|}$

Neste contexto, segue a definição do problema de encontrar um subgrafo de maior densidade:

• Entrada: Grafo não-direcionado $G(V,E)$
• Saída: Subconjunto de vértices $Sopt \subseteq V$ que produz um subgrafo de menor densidade $r(Sopt)$.

Este é um exemplo de problema no qual existe solução polinomial determinística, entretanto, para grafos muito grandes mesmo a solução polinomial (tipicamente no máximo quadrática) se torna inviável. O objetivo deste exercício é a implementação e a experimentação com um algoritmo 3-aproximativo para o problema do subgrafo de maior densidade.

Exercício 1: algoritmo 3-aproximativo baseado em escolha gulosa¶

sequential-peeling(G(V,E))
S = V
Sopt = S
while S != {}
  u = "vértice u de menor grau em S"
  S = S \ {u}                           // isso gera remoção de arestas
  if r(S) > r(Sopt)
    Sopt = S                            // copia melhor subgrafo
return Sopt

Você deve construir um programa em C/C++ com nome greedy_peeling.cpp que receba na entrada padrão uma lista de arestas de um grafo não-direcionado e produza na saída: (1) densidade do subgrafo $Sopt$ encontrado; (2) lista de vértices que produziram essa densidade. Dica: implemente o algoritmo usando uma fila de prioridades.

O formato de um arquivo de entrada pode ser encontrado este grafo de colaboração do repositório SNAP.

O formato do arquivo de saída, duas linhas contendo:

<densidade: número real>
<lista de vértices de Sopt separados por espaço>

Exercício 2: experimentos com mais grafos¶

Neste link, na seção chamada “Collaboration networks” você vai encontrar outros grafos para teste além do ca-AstroPh. Execute o seu algoritmo para, pelo menos, mais dois grafos.