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
Respostas:
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) k k
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) s n−2 s n−2
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,V∖C) C V∖C
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,V∖C) C V∖C
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,V∖C) G s k G s
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,V∖C) s T1 T2 C V∖C T1 T2 |T1|+|T2|=|C|−1+|V∖C|−1=|V|−2=k (C,V∖C) s s
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 ) sk G s k k=n−2 C V∖C (C,V∖C) . 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 / 100N≥1 P(N) A B N A B P(N) A B N2 N2−N/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) G P(N) A B v∈V A B
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 + ns≥0 (C,V∖C) G s G′ s+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,V∖C) G s (A∪C,B∪V∖C) G′ G′ s C V∖C N2 A B n 2n V A∪B
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 AG′ s+N2+n A B P(N) N2−N/100 P(N) N2−N/100+|E|+2|V|≤N2−N/100+n2+2n=N2 C V A N2 A BB nn VV A∪BA∪B , de modo que deve ser, pelo menos, de para .ss CC V∖CV∖C
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.
fonte