Maximizar pesos de borde de suma

Me pregunto si el siguiente problema tiene un nombre o algún resultado relacionado con él.

Sea un gráfico ponderado donde denota el peso del borde entre y , y para todos , . El problema es encontrar un subconjunto de vértices que maximice la suma de los pesos de los bordes adyacentes a ellos: Tenga en cuenta que estoy contando los bordes que están dentro del subconjunto y que están fuera del subconjunto, que es lo que distingue este problema de max-cut. Sin embargo, incluso si tanto como están en , solo quiero contar el borde $G = (V,w)$ $w(u,v)$ $u$ $v$ $u,v \in V$ $w(u,v) \in [-1,1]$

max_{S \subseteq V} \sum_{(u, v) : u \in S or v \in S} w (u, v)

$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$

u

$u$

v

$v$

S

$S$

(u, v)

$(u,v)$ una vez (en lugar de dos veces), que es lo que distingue el objetivo de ser simplemente la suma de los grados.

Tenga en cuenta que el problema es trivial si todos los pesos de los bordes no son negativos, ¡simplemente tome el gráfico completo!

reference-request graph-theory approximation-algorithms terminology approximation-hardness Aaron Roth
fuente

Su definición no coincide con su nota más adelante sobre no contar los bordes duplicados. ¿Está sumando sobre pares ordenados o subconjuntos de 2 elementos? (este último le daría la propiedad que necesita, creo)

Suresh Venkat

Otra nota: los únicos pesos de borde NO contados son aquellos dentro de V \ S. ¿Está interesado en resultados de dureza o aproximaciones, porque en el primer caso, minimizar la suma de pesos de borde dentro de S '= V \ S podría ser el problema más natural? .

Suresh Venkat

@Suresh: La definición formal en la pregunta es correcta en lo que respecta a la relación de aproximación. Simplemente da exactamente el doble de lo que uno espera de las palabras.

Tsuyoshi Ito

@ TsuyoshiIto: oh, ya veo, porque los bordes del corte también se cuentan dos veces.

Suresh Venkat

El problema exacto es NP-hard porque, como Suresh escribió en su comentario, el problema es equivalente a la programación cuadrática {0,1} sin restricciones, que es NP-hard.

Tsuyoshi Ito

Respuestas:

No es realmente una solución, sino algunas observaciones.

Este es un caso especial del siguiente problema: dado un universo , y una colección de conjuntos , y una función de peso , encuentre el conjunto modo que esté maximizado (el peso de un conjunto es el peso total de sus elementos). Su problema corresponde al caso en el que cada elemento de aparece exactamente en dos conjuntos (pero no estoy seguro de cómo explotar esta restricción, aunque podría ayudar). $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})$ $U$

Este es un problema de cobertura: similar a Max-k-Set-Cover, pero sin la restricción de usar sets y con pesos negativos permitidos. La aproximación codiciosa de Max-k-Set-Cover (en cada paso genera el conjunto que tiene el mayor peso de elementos descubiertos hasta el momento) genera una secuencia de conjuntos de modo que los primeros conjuntos sean una aproximación óptimo (por lo que esta es una aproximación simultánea para todos los ). Desafortunadamente, como de costumbre, hay un problema al analizarlo cuando los pesos pueden ser negativos. La observación básica del análisis del algoritmo codicioso es que si es el primer conjunto que se emite, entonces ( $k$ $k$ $1 + 1/e$ $k$ $S_1$ $w(S_1) \geq OPT_k/k$ $OPT_k$ siendo el peso máximo cubierto por conjuntos), porque es menor que la suma de los pesos de los conjuntos en la solución óptima, y cada uno de ellos tiene un peso menor que . Sin embargo, con pesos negativos ya no es cierto que es menor que la suma de los pesos en la solución óptima. En general, un enlace sindical ya no es cierto. $k$ $OPT_k$ $k$ $w(S_1)$ $OPT_k$

Sasho Nikolov
fuente

FWIW, su problema es difícil de aproximar dentro de un factor multiplicativo de para cualquier . $n^{1-\epsilon}$ $\epsilon>0$

Demostramos eso a continuación al dar una reducción de preservación de la aproximación del Conjunto Independiente, para lo cual se conoce la dureza de la aproximación.

Reducción del conjunto independiente

Deje que el gráfico no dirigido sea una instancia de Conjunto Independiente. Deje denotar el grado de vértice en . Deje que es el número de vértices en . $G=(V,E)$ $d_v$ $v$ $G$ $n$ $G$

Construya el gráfico ponderado de borde partir de siguiente manera. Asigne a cada borde en peso 1. Para cada vértice no aislado , agregue nuevos bordes, cada uno con un peso , a nuevos vértices. Para cada vértice aislado , agregue un nuevo borde de peso 1 a un nuevo vértice. $G'=(V',E')$ $G$ $E$ $v\in V$ $d_v-1$ $-1$ $d_v-1$ $v\in V$

(Nota: cada nuevo vértice (en pero no ) tiene exactamente un vecino, que está en ). $G'$ $G$ $G$

Lema tiene un conjunto independiente de tamaño iff (como una instancia de su problema) tiene una solución de valor al menos . $G$ $k$ $G'$ $k$

Prueba. Deje ser cualquier conjunto independiente de . Entonces, dado que los vértices en son independientes en , el valor de en (según su objetivo) es $S$ $G$ $S$ $G'$ $S$ $G'$

\sum_{v \in S} d_{v} - (d_{v} - 1) = | S | .

$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$

Por el contrario, que sea una solución para de valor al menos . Sin pérdida de generalidad, suponga que no contiene vértices nuevos. (Cada nuevo vértice está en un solo borde . Si no estaba aislado en , entonces el peso del borde es , por lo que eliminar de aumenta el valor de Si se aisló, entonces el peso del borde es 1, por lo que eliminar de y agregar mantiene el valor de ). $S$ $G'$ $k$ $S$ $v'$ $(v',v)$ $v$ $G$ $-1$ $v'$ $S$ $S$ $v$ $v'$ $S$ $v$ $S$

Sin pérdida de generalidad, se supone que es un conjunto independiente en . (De lo contrario, sea un borde tal que y estén en El peso total de los bordes incidentes de en es , entonces el peso total de Los bordes incidentes distintos de son como máximo cero. Por lo tanto, eliminar de no aumentaría el valor de ). $S$ $G$ $(u,v)$ $u$ $v$ $S$ $v$ $G'$ $d_v - (d_v-1) = 1$ $v$ $(u,v)$ $v$ $S$ $S$

Ahora, por el mismo cálculo que al comienzo de la prueba, el valor de es. Se deduce que . QED $S$ $|S|$ $|S| \ge k$

Como comentario adicional, puede solicitar una aproximación aditiva , por ejemplo, o . $O(n)$ $\epsilon m$

Me parece posible que para su problema, incluso decidir si hay una solución de valor positivo podría ser NP-hard.

Neal Young
fuente