Problema de subgrafo conectado de peso máximo em gráficos planares

O problema do subgráfico conectado de peso máximo é o seguinte:

Entrada: um gráfico e um peso (possivelmente negativo) para cada vértice .w i i ∈ $G=(V,E)$$w_i$$i \in V$

Saída: um subconjunto de peso máximo de vértices, de modo que esteja conectado.G [ S $S$$G[S]$

Este problema é NP-difícil. David S. Johnson menciona na pág. 149 desta coluna que o problema permanece difícil em gráficos planares de grau máximo três com todos os pesos ou .- $+1$$-1$

Não consigo encontrar o artigo citado - A. Vergis, manuscrito (1983)

Alguma idéia de onde encontrar o jornal? Ou qual foi a redução?

Na coluna "A NP-Completeness: Um Guia Contínuo", número 14, Johnson escreve "... Vergis [49]. Transformação de STEINER TREE EM GRAPHS [ND12] ..." . Não tenho acesso ao artigo da Vergis, no entanto, uma possível redução pode ser a seguinte.

Árvore Steiner (ST) no problema de gráficos

Instância : um gráfico não direcionado , um subconjunto dos vértices R ⊆ V , chamados nós terminais ; um número inteiro não negativo $G = (V,E)$$R \subseteq V$$k$

Pergunta : existe uma subárvore de que inclui todos os vértices de R (uma árvore de abrangência para R ) e que contém no máximo k arestas?$G$$R$$R$$k$

O problema continua sendo o NPC, mesmo para gráficos planares (M. Garey e D. Johnson. O problema retilíneo das árvores de Steiner é NP-completo).

Dada uma instância do ST planar, por enquanto, suponha que você possa atribuir pesos arbitrários aos nós. Se e | E | = q , você pode atribuir peso q + 1 aos nós de R e adicionar um nó do meio a cada extremidade de E e atribuir peso - 1 a ele. Atribuir peso 0 para os restantes nós em V ∖ R . O gráfico original G tem uma árvore de abrangência para R com no máximo $|R|=p$$|E|=q$$q+1$$R$$E$$-1$$0$$V \setminus R$$G$$R$$k$arestas se e somente se no gráfico transformado você puder encontrar um subgrafo de peso alvo maior ou igual a .$W = p(q+1) - k$

Informalmente, para atingir a quantidade de você deve incluir todos os nós de R no subgráfico e deve incluir no máximo k nós do meio (correspondentes às arestas de G ) que têm peso negativo -1 para mantê-los conectados .$p(q+1)$$R$$k$$G$

Você pode reduzir o grau máximo do gráfico inteiro para três desta maneira: se apenas transforme cada nó u i em uma cadeia circular de nós D (e ajuste o valor de p de acordo). Conecte as arestas de entrada a nós distintos da cadeia (que terão o grau 3).$D = \max\{deg(u_i) \mid u_i \in V\}$$u_i$$D$$p$

E se você deseja usar apenas pesos , deve: (A) atribuir + 1 a todos os nós das cadeias circulares correspondentes aos nós em V ∖ R , (B) transformar cada nó do meio em uma cadeia linear de nós de peso - 1 e comprimento l E = | V ∖ R | + 1 e (C) expandem ainda mais as cadeias circulares (com peso +1) correspondentes aos nós de R com pelo menos comprimento l R$+1,-1$
$+1$$V\setminus R$
$-1$$l_E = |V\setminus R|+1$
$R$ ; e conjunto peso alvo W = P l R - K L E . Informalmente, as cadeias expandidas e o novo alvo tornam ospesos + 1 dos nós correspondentes a V ∖ R (ponto A) irrelevantes.$l_R = l_E( |E| + 1)$$W =pl_R - kl_E$
$+1$$V \setminus R$