Um problema multicortado

12

Estou procurando um nome ou qualquer referência a esse problema.

Dado um gráfico ponderado, G=(V,E,w) encontre uma partição dos vértices em até n=|V|define S1,,Sn para maximizar o valor das arestas de corte:

c(S1,,Sn)=ij((u,v)E:uSi,vSjw(u,v))
Observe que alguns dos conjuntosSipodem estar vazios. Portanto, o problema é essencialmente o corte máximo de k, exceto queknão faz parte da entrada: o algoritmo pode escolher qualquerkquedesejar, de modo a maximizar o valor das arestas de corte. Obviamente, o problema é trivial se os pesos das arestas não forem negativos: basta colocar todos os vértices sozinhos em seu próprio conjunto e você cortará todas as arestas. Mas, para tornar as coisas interessantes, arestas de peso negativo são permitidas.

Esse é um problema estudado? Serão apreciadas referências a resultados algorítmicos ou de dureza!

Aaron Roth
fonte
2
+11G±1

Respostas:

11

O problema é uma variante de Correlation Clustering (CC) Bansal, N., Blum, A. e Chawla, S. (2004). "Clustering de correlação". Jornal de Aprendizado de Máquina (Edição Especial sobre Avanços Teóricos no Agrupamento de Dados, pp. 86-113, doi: 10.1023 / B: MACH.0000033116.57574.95.

G(v,w)a(v,w)b(v,w)PcP(v,w)a(v,w)vwPb(v,w)PVv,wc(v,w)

a(v,w)=0b(v,w)O(logn)

Os PTASs descritos são baseados na técnica de programação polinomial suave: no caso mais geral, não acho que seu problema atenda aos requisitos da técnica.

Gianluca Della Vedova
fonte
18

Não conheço nenhuma referência, mas posso mostrar que é NP-completo, através de uma redução na coloração do gráfico.

Dado um gráfico G e um número k de cores com as quais colorir G, faça um novo gráfico G 'que consiste em G junto com k novos vértices, de modo que cada novo vértice seja conectado a todos os vértices em G. Atribua peso + kn a cada aresta de G, peso + kn para cada aresta conectando dois dos k novos vértices e peso -1 para cada uma das arestas conectando os k novos vértices a G.

Então, se G puder ser colorido em k, a coloração (junto com uma partição que atribui cada um dos novos vértices a uma das classes de cores) atinge o peso total kn (m + k (k-1) / 2) - (k -1) n.

Na outra direção, se você tiver uma partição que atinja esse peso total, deverá cortar todas as arestas de G e todas as arestas entre pares de novos vértices. Cortar todas as arestas de G define uma coloração de G, e arestas de corte entre pares de novos vértices implica que cada vértice de G pode ser adjacente a no máximo um dos k novos vértices. Portanto, para obter o termo ideal - (k-1) n no peso, cada vértice de G deve estar adjacente a exatamente um dos novos vértices e, portanto, só pode haver k classes de cores na coloração definida pelo partição.

Ou seja, partições com o limite de peso especificado estão em correspondência 1-1 com k-colorações de G, portanto, isso define uma redução da coloração para o problema da partição.

David Eppstein
fonte
11

Deixe-me complementar a boa prova de completude de NP de David, adicionando uma referência ao caso especial solicitado por Jukka em um comentário sobre a pergunta. Se o gráfico for o gráfico completo e os pesos das arestas forem restritos a ± 1, o problema será equivalente ao problema NP-complete, conhecido como Edição de Cluster.

A edição de cluster é o seguinte problema introduzido por Shamir, Sharan e Tsur [SST04]. Aqui, um gráfico de cluster é um gráfico que é uma união de cliques separados por vértices e uma edição é a adição ou a remoção de uma aresta.


Instância de edição de cluster : Um gráfico G = ( V , E ) e um número inteiro k ∈ℕ.
Pergunta : É possível transformar G em um gráfico de cluster no máximo em k edições?

A edição de cluster está completa com NP [SST04].

Para ver a Edição de Cluster é equivalente ao caso especial acima mencionado do problema atual, seja G = ( V , E ) um gráfico. Seja n = | V | e considere G como um subgráfico do gráfico completo K n . Em K n , dão o peso -1 para as bordas em L e o peso 1 para as extremidades não em G . Então G pode ser transformado em um gráfico de cluster por no máximo k edições, se e somente se existir uma partição ( S 1 ,…, S n ) tal que c ( S 1 ,…,S n ) ≥ - | E | - k para este gráfico completo ponderado K n .(n2)

[SST04] Ron Shamir, Roded Sharan e Dekel Tsur. Problemas de modificação do gráfico de cluster. Matemática Aplicada Discreta , 144 (1–2): 173–182, novembro de 2004. http://dx.doi.org/10.1016/j.dam.2004.01.007

Tsuyoshi Ito
fonte