Aumentando a capacidade de maximizar o corte mínimo

9

Considere um gráfico com todas as arestas com capacidade unitária. Pode-se encontrar o corte mínimo no tempo polinomial.

Suponha que eu possa aumentar a capacidade de qualquer arestas até o infinito (equivalente a mesclar os nós em ambos os lados da aresta). Qual é a maneira ideal de selecionar um conjunto ideal de arestas (cuja capacidade será aumentada até o infinito) para maximizar o corte mínimo?k kkk

user14373
fonte
Não sei se entendi sua pergunta: por "Qual é a maneira ideal de selecionar k tais arestas para maximizar o corte mínimo?", Você quer dizer o corte mínimo de 1) um gráfico com capacidades unitárias ou 2) um gráfico com capacidades gerais ?
28413 Jeremy

Respostas:

3

Teorema. O problema no post é difícil de NP.

Por "o problema no post", quero dizer, dado um gráfico e um número inteiro , para escolher arestas para aumentar as capacidades de modo a maximizar o corte mínimo no gráfico modificado.G = ( V , E ) k kG=(V,E)kk

A idéia é reduzir do Max Cut. Aproximadamente, um determinado gráfico tem o tamanho máximo de corte se e somente se você pode aumentar as capacidades das arestas para que o gráfico resultante tenha o tamanho mínimo de corte . A idéia é que arestas são suficientes para forçar o gráfico resultante a ter apenas um corte de capacidade finita e esse pode ser o corte que você escolher.G = ( V , E ) s n - 2 s n - 2G=(V,E)sn2sn2

Essa ideia não funciona porque, para obter um determinado corte , é necessário conectar os subgráficos induzidos por eMas você pode contornar isso com um gadget apropriado.( C , V C ) C V C(C,VC)CVC

Prova. Dado um gráfico conectado G = ( V , E ) , defina um corte conectado como sendo um corte ( C , V C ), de modo que os subgráficos induzidos por C e por V C sejam conectados. Defina Max Connected Cut como o problema de encontrar um corte conectado (em um determinado gráfico conectado) maximizando o número de arestas que cruzam o corte.G=(V,E)( C,VC)CVC

Mostramos que o Max Connected Cut se reduz ao problema no post. Em seguida, mostramos que o Max Cut não ponderado se reduz a Max Connected Cut.

Lema 1. O Max Connected Cut reduz o tempo de poli ao problema definido no post.

Prova. Dada uma instância Max-Connected-Cut G = ( V , E ) , deixe k = | V | - 2 . Para provar o lema, provamos o seguinte:G=(V,E)k=|V|2

Reivindicação 1: Para qualquer s > 0 , há um corte conectado em de capacidade, pelo menos , IFF, é possível aumentar capacidades de aresta em para o infinito, para que o gráfico resultante tenha mín. capacidade de corte pelo menos .s>0( C , V C ) G s k G s(C,VC)GskGs

SOMENTE SE: Suponha que haja um corte conectado de capacidade pelo menos . Seja e subárvores que abranjam, respectivamente, e , e aumente a capacidade das arestas em e . (Observe que .) O único corte de capacidade finita restante no gráfico é então , com capacidade de pelo menos , portanto, o gráfico resultante tem capacidade de corte mínima de pelo menos .( C , V C ) s T 1 T 2 C V C T 1 T 2 | T 1 | + | T 2 | = | C | - 1 + | V C | - 1 = | V | - 2 = k ( C , V C ) s s(C,VC)sT1T2CVCT1T2|T1|+|T2|=|C|1+|VC|1=|V|2=k(C,VC)ss

IF: Suponha que seja possível aumentar capacidades da aresta em para que o gráfico resultante tenha capacidade de corte mínima de pelo menos . Considere o subgráfico formado pelas arestas elevadas. Sem perda de generalidade, assuma que este subgráfico é acíclico. (Caso contrário, "desenrole" uma aresta de um ciclo de arestas elevadas e, em vez disso, levante uma aresta não levantada que une dois componentes conectados do subgráfico. Isso só aumenta o corte mínimo no gráfico resultante.) Ao escolher , o subgráfico de arestas elevadas possui dois componentes conectados, como e , portanto, o único corte de capacidade finita no gráfico resultante ék G s k k = n - 2 C V C ( C , V C ) skGskk=n2CVC(C,VC). E esse corte tem capacidade pelo menos , como no gráfico original.s

Isso prova a afirmação (e o lema). (QED)

Para garantir a integridade, mostramos que o Max Connected Cut é NP-completo, por redução do Max Cut não ponderado.

Lema 2. O Max Cut não ponderado reduz o tempo de poli ao Max Connected Cut .

Prova. Para qualquer inteiro , definir gráfico para consistir em dois caminhos e , cada um de comprimento , com arestas de cada vértice de para cada vértice em . Deixamos como um exercício para o leitor verificar se o corte máximo em ( de um lado, do outro) tem tamanho , e nenhum outro corte tem tamanho maior que, digamos, .N 1 P ( N ) A B N A B P ( N ) A B N 2 N 2 - N / 100N1P(N)ABNABP(N)ABN2N2N/100

Aqui está a redução. Dada qualquer instância Max Cut não ponderada , construa um gráfico seguinte maneira. Seja. Seja . Adicione a o gráfico definido acima (com seus dois caminhos e ). A partir de cada vértice adicionar uma borda para um vértice de e outro bordo de um vértice em . Isso define a redução. Para finalizar, provamos que está correto:G = ( V , E ) G = ( V , E ) n = | V | N = 100 ( n 2 + 2 n ) G P ( N ) A B v V A BG=(V,E)G=(V,E)n=|V|N=100(n2+2n)GP(N)ABvVAB

Reivindicação 2: para qualquer , há um corte em de capacidade pelo menos , IFF há um corte conectado em de tamanho pelo menos .s 0 ( C , V C ) G s G s + N 2 + ns0(C,VC)GsGs+N2+n

SOMENTE SE: Dado qualquer corte em de capacidade, pelo menos , considere o corte conectado em . Este corte conectado em cortes, pelo menos, bordas de para , além de extremidades de a , além de das bordas de para .( C , V C ) G s ( A C , B V C ) G G s C V C N 2 A B n 2 n V A B(C,VC)Gs(AC,BVC)GGsCVCN2ABn2nVAB

SE: Suponha que exista um corte conectado em de tamanho pelo menos . e estão em lados opostos do corte. (Caso contrário, como o segundo maior corte em corta no máximo arestas em , o número total de arestas cortadas é no máximo ) Let. denotar os vértices em no lado do corte com . Depois, há bordas do corte de a , e a partir de paraG s + N 2 + n A B P ( N ) N 2 - N / 100 P ( N ) N 2 - N / 100 + | E | + 2 | V | N 2 - N / 100 + n 2 + 2 n = N 2 C V A N 2 AGs+N2+nABP(N)N2N/100P(N)N2N/100+|E|+2|V|N2N/100+n2+2n=N2CVAN2ABBnnVVABAB , de modo que deve ser, pelo menos, de para .ssCCVCVC

Isso prova a reivindicação e o Lema 2. (QED)

Nos lemas 1 e 2, como o Max Cut não ponderado é difícil para NP, o problema no post também é difícil para NP.

Neal Young
fonte
Isto também mostra que as "bordas incrementando k para maximizar o r corte" problema para dado s e t é NP-completo (pick s e t de ser vértices A e B respectivamente). sts
Daniello