Maximizando os pesos das arestas da soma

Gostaria de saber se o seguinte problema tem um nome ou quaisquer resultados relacionados a ele.

Deixe $G = (V,w)$ ser um gráfico ponderada onde $w(u,v)$ indica o peso da aresta entre $u$ e , e para todo , . O problema é encontrar um subconjunto de vértices que maximize a soma dos pesos das arestas adjacentes a eles: Observe que estou contando as arestas que estão dentro do subconjunto e fora do subconjunto, que é o que distingue esse problema do corte máximo. No entanto, mesmo se ambosu , v ∈ V w ( u , v ) ∈ [ - 1 , 1 ] max S ⊆ V ∑ ( u , v ) : u ∈ S ou v ∈ S w ( u , v ) u v S ( u , v $v$$u,v \in V$$w(u,v) \in [-1,1]$

Observe que o problema é trivial se todos os pesos das arestas não forem negativos - basta pegar o gráfico inteiro!

Não é realmente uma solução, mas algumas observações.

Este é um caso especial do seguinte problema: dado um universo e uma coleção de conjuntos S 1 , … , S n ⊆ U e uma função de peso w : U → [ - 1 , 1 ] , encontre o conjunto I ⊆ [ n ] tal que w ( ⋃ i ∈ I S i$U = \{1, \ldots, m\}$$S_1, \ldots, S_n \subseteq U$$w:U \rightarrow [-1, 1]$$I \subseteq [n]$$w(\bigcup_{i \in I}{S_i})$é maximizado (o peso de um conjunto é o peso total de seus elementos). Seu problema corresponde ao caso em que cada elemento de aparece exatamente em dois conjuntos (mas não sei como explorar essa restrição, embora possa ajudar).$U$

Esse é um problema de cobertura: semelhante ao Max-k-Set-Cover, mas sem a restrição de uso de sets e com pesos negativos permitidos. A aproximação gananciosa de Max-k-Set-Cover (em cada etapa gera o conjunto que tem o maior peso de elementos descobertos até agora) gera uma sequência de conjuntos, de modo que os primeiros k conjuntos sejam uma aproximação 1 + 1 / e à ideal (portanto, é uma aproximação simultânea para todos os k ). Infelizmente, como sempre, há um problema em analisá-lo quando os pesos podem ser negativos. A observação básica da análise do algoritmo guloso é que, se S 1 é o primeiro conjunto a ser produzido, então w $k$$k$$1 + 1/e$$k$$S_1$ ( O P T k é o peso máximo coberto por k conjuntos), porque O P T k é menor que a soma dos pesos dos k conjuntos na solução ideal e cada um deles eles têm peso menor que w ( S 1 ) . No entanto, com pesos negativos, não é mais verdade que O P T k é menor que a soma dos pesos na solução ideal. Em geral, um limite de união não é mais verdadeiro.$w(S_1) \geq OPT_k/k$$OPT_k$$k$$OPT_k$$k$$w(S_1)$$OPT_k$

FWIW, é difícil aproximar seu problema com um fator multiplicativo de para qualquer ϵ > 0 .$n^{1-\epsilon}$$\epsilon>0$

Mostramos isso abaixo, fornecendo uma redução de preservação de aproximação do Independent Set, pela qual a dureza da aproximação é conhecida.

Redução do conjunto independente

Seja o gráfico não direcionado uma instância do Conjunto Independente. Deixe d v significam o grau de vértice v em L . Deixe que n seja o número de vértices em L .$G=(V,E)$$d_v$$v$$G$$n$$G$

Construa o gráfico ponderado pela aresta partir de G da seguinte maneira. Dê a cada aresta o peso E 1. Para cada vértice não isolado v ∈ V , adicione d v - 1 novas arestas, cada uma com peso - 1 , a d v - 1 novos vértices. Para cada vértice isolado v ∈ V , adicione uma nova aresta de peso 1 a um novo vértice.$G'=(V',E')$$G$$E$$v\in V$$d_v-1$$-1$$d_v-1$$v\in V$

(Nota: cada novo vértice (em mas não G ) tem exatamente um vizinho, que está em G ).$G'$$G$$G$

Lema. tem um conjunto independente de tamanho k, se G ' (como uma instância do seu problema) tem uma solução de valor pelo menos k .$G$$k$$G'$$k$

Prova. Deixe- ser qualquer conjunto independente em G . Então, como os vértices em S são independentes em G ′ , o valor de S em G ′ (pelo seu objetivo) é ∑ v ∈ S d v - ( d v - 1 ) = | S | $S$$G$$S$$G'$$S$$G'$

Por outro lado, seja uma solução para G ' de valor pelo menos k . Sem perda de generalidade, suponha que S não contenha novos vértices. (Cada novo vértice v ′ está em uma única aresta ( v ′ , v ) . Se v não foi isolado em G , então o peso da aresta é - 1 , portanto, remover v ′ de S aumenta o valor de S. Se v foi isolado, então o peso da borda é 1, removendo v $S$$G'$$k$$S$$v'$$(v',v)$$v$$G$$-1$$v'$$S$$S$$v$$v'$de e a adição de v mantém o valor de S. )$S$$v$$S$

Sem perda de generalidade, assuma que é um conjunto independente em G . (Caso contrário, seja ( u , v ) uma aresta de modo que u e v estejam em S. O peso total das arestas incidentes de v em G ′ é d v - ( d v - 1 ) = 1 , então o peso total de v 's incidente arestas diferente ( u , v ) é, no máximo a zero. Assim, a remoção $S$$G$$(u,v)$$u$$v$$S$$v$$G'$$d_v - (d_v-1) = 1$$v$$(u,v)$$v$de não aumentaria o valor de S. )$S$$S$

Agora, pelo mesmo cálculo que no início da prova, o valor de é | S | . Segue-se que | S | ≥ k . QED$S$$|S|$$|S| \ge k$

Como um aparte, você pode pedir uma aproximação aditiva de, digamos, ou ϵ m . $O(n)$$\epsilon m$

Parece-me possível que, para o seu problema, decidir se existe uma solução de valor positivo possa ser difícil para o NP.