Problema de subgrafo conectado de peso máximo en gráficos planos

El problema del subgrafo conectado de peso máximo es el siguiente:

Entrada: un gráfico y un peso (posiblemente negativo) para cada vértice .$G=(V,E)$$w_i$$i \in V$

Salida: un subconjunto de pesos máximos de vértices tal que está conectado.$S$$G[S]$

Este problema es NP-hard. David S. Johnson menciona en la pág. 149 de esta columna que el problema sigue siendo difícil en los gráficos planos de grado máximo tres con todos los pesos, ya sea$+1$ o $-1$ .

No puedo encontrar el artículo citado: A. Vergis, manuscrito (1983)

¿Alguna idea de dónde encontrar el papel? ¿O cuál fue la reducción?

En la columna "La NP-Completitud: una guía en curso" número 14, Johnson escribe "... Vergis [49]. Transformación de STEINER TREE EN GRÁFICOS [ND12] ..." . No tengo acceso al documento de Vergis, sin embargo, una posible reducción puede ser la siguiente.

Steiner Tree (ST) en problema de gráficos

Instancia : un gráfico no dirigido , un subconjunto de los vértices R ⊆ V , llamados nodos terminales ; un entero no negativo $G = (V,E)$$R \subseteq V$$k$

Pregunta : ¿hay un subárbol de que incluya todos los vértices de R (un árbol de expansión para R ) y que contenga como máximo k aristas?$G$$R$$R$$k$

El problema sigue siendo NPC incluso para los gráficos planos (M. Garey y D. Johnson. El problema del árbol rectilíneo de Steiner es NP-completo).

Dada una instancia de ST plano, por ahora suponga que puede asignar pesos arbitrarios a los nodos. Si y | E | = q , puede asignar peso q + 1 a los nodos de R y puede agregar un nodo intermedio a cada borde de E y asignar peso - 1 a él. Peso Assign 0 a los nodos restantes en V ∖ R . El gráfico original G tiene un árbol de expansión para R con como máximo $|R|=p$$|E|=q$$q+1$$R$$E$$-1$$0$$V \setminus R$$G$$R$$k$aristas si y solo si en el gráfico transformado puede encontrar una subgrafía de peso objetivo mayor o igual a .$W = p(q+1) - k$

Informalmente para alcanzar la cantidad debe incluir todos los nodos de R en el subgrafo, y debe incluir a lo sumo k nodos medios (correspondientes a los bordes de G ) que tienen un peso negativo -1 para mantenerlos conectados .$p(q+1)$$R$$k$$G$

Puede reducir el grado máximo de todo el gráfico a tres de esta manera: si simplemente transforme cada nodo u i en una cadena circular de D nodos (y ajustar el valor de p en consecuencia). Conecte los bordes entrantes a nodos distintos de la cadena (que tendrá un grado 3).$D = \max\{deg(u_i) \mid u_i \in V\}$$u_i$$D$$p$

Y si desea usar solo pesos , debe: (A) asignar + 1 a todos los nodos de las cadenas circulares correspondientes a los nodos en V ∖ R , (B) transformar cada nodo medio en una cadena lineal de nodos de peso - 1 y longitud l E = | V ∖ R | + 1 y (C) expanden aún más las cadenas circulares (con peso +1) correspondientes a los nodos de R a al menos longitud l R$+1,-1$
$+1$$V\setminus R$
$-1$$l_E = |V\setminus R|+1$
$R$ ; y conjunto objetivo de peso W = p l R - k l E . Informalmente, las cadenas expandidas y el nuevo objetivo hacen que lospesos + 1 de los nodos correspondientes a V ∖ R (punto A) sean irrelevantes.$l_R = l_E( |E| + 1)$$W =pl_R - kl_E$
$+1$$V \setminus R$