Algoritmo eficiente para corte min com número especificado de vértices

Question

Considere um gráfico com vértices $ v $ e bordas $ e $ . A versão padrão do problema de corte min é para encontrar a partição da $ v $ em um subconjunto (não vazio) $ C $ e seu complemento $ \ bar {c} $ de modo a minimizar o número de bordas que vão entre $ C $ e $ \ bar {c} $ . Algoritmos são conhecidos por este problema que resolvizá-lo em tempo polinômio. Minha pergunta é, e se um adicionalmente especifica a restrição que $ | c |= n $ para alguma $ n <| v | $ ? Ou seja, desejamos encontrar o conjunto de $ n $ vértices com o número mínimo de bordas conectando-o ao resto dos vértices. Existem também algoritmos eficientes para este caso? Estou interessado tanto na questão de saber se este problema é formalmente solucionável em tempo polinomial (que eu acho que é) e também em que algoritmos são melhor na prática.

Answer 1

Para $ n=frac {| v |} 2 $ , é chamado de bissecção mínima, e é np-hard. Existe uma $ o (\ log ^ {3/2} n) $ -adequação: " uma aproximação polilogarítmica do bisseco mínimo ".

Se você estiver interessado, o problema mais geral é dividir vários componentes do mesmo tamanho, e é chamado de particionamento balanceado do gráfico. Por mais de 2 partes, não existe uma aproximação finita a menos que p= np: "particionamento de gráfico balanceado" (Andreev, rakke) , já que você não pode verificar eficientemente se a resposta é 0.

Se as peças não forem necessariamente exatamente equilibradas (um pequeno desequilíbrio é permitido), uma $ o (\ log n) $ - Algoritmo de aprovação existe: "Partições equilibradas de árvores e aplicações" .

---

.

Alguns algoritmos (também cheque https://en.wikipedia.org/wiki/graph_partition e "referências" seções dos seguintes artigos):

• Pesquisa local com vários sabores: começamos com algum particionamento e tentamos trocar vértices entre as partes para minimizar o corte. Por exemplo. Nós computar "ganho" para cada vértice (melhoria se a movimentarmos para outra parte), e trocar vértices com o ganho máximo. Sua vantagem é que você pode aplicá-lo após qualquer outro algoritmo.

• particionamento espectral (ver, por exemplo, teoria e gráfico de gráfico espectral Particionamento ): usa o segundo eigenvetor de uma matriz laplaciana para aproximar a partição (por exemplo, movendo a menor $ | v | / 2 $ coordenadas para o primeiro papel). Funciona surpreendentemente bem. No entanto, não tenho certeza se pode ser adaptado ao caso quando quiser uma bissecção desequilibrada (por exemplo, $ 1: 2 $ em vez de recipiente de matemática $ 1: 1 $ ).

• incorporação linear: "particionamento balanceado distribuído via incorporação linear" . Nós incorporamos vértices em uma matriz unidimensional enquanto minimizando soma sobre todos os pares de vértices: a distância entre eles multiplicada pelo peso de sua borda. Então nós apenas dividimos essa matriz em pedaços consecutivos de tamanhos necessários. Não funcionou tão bem na minha experiência.

• (anúncios) Nosso papel: gráfico balanceado multidimensional Particionamento via Descida de gradiente projetada ", onde usamos a descida de gradiente para encontrar bissection mínimo: para cada vértice, introduzimos uma variável que representa uma probabilidade que o vértice pertence à primeira parte, e minimizando o corte reduz a otimização restrita de um função quadrática. É um pouco superado na prática por uma pesquisa local ajustada, mas funciona muito bem quando você tem várias restrições de equilíbrio.

Além do método espectral, todos podem ser trivialmente adaptados para particionar o gráfico em proporções arbitrárias.

Há também solucionadores padrão: kahip , metis . Na minha experiência, Kahip era muito bom. Não tenho certeza se eles apóiam a divisão em partes de tamanhos arbitrários.