Cómo encontrar un subgrafo de camarillas con el mínimo peso de la suma total

Question

Supongamos que nos dan una gráfica de $N$ vértices $V_1, \ldots, V_N$ . Para cada vértice $V_i$ hay un peso correspondiente $v_i$ . Para un gráfico de $N$ vértices, queremos encontrar el subgrafo de peso mínimo formado por camarillas disjuntas que incluya todos los vértices (es decir, todos los vértices están presentes en el subgrafo y cada vértice está exactamente en una camarilla) bajo dos condiciones siguientes:

1. Para cada camarilla (subgrafo completo) del gráfico original, el peso se define como el máximo de los pesos de los vértices de la camarilla. Más concretamente, si los vértices $X_1, \ldots, X_k$ forman una camarilla en la que $x_i$ es el peso del vértice $X_i$ entonces el peso de esta camarilla es $\max\{x_1,\ldots,x_k \}$ .
2. El peso total de un subgrafo con múltiples camarillas es la suma de los pesos de las camarillas.

Quiero saber si este problema es NP-completo. ¿Existe algún algoritmo de aproximación para este problema que se ejecute en tiempo polinómico de $N$ .

Answer 1

El caso especial cuando el peso de cada vértice $v_i$ es igual a $1$ se resume en resolver el siguiente problema: particionar los vértices en camarillas y minimizar el número de camarillas.

Esto se conoce como el problema de la cubierta de la camarilla de vértices ( ver aquí ). [Editar: es sencillo ver que Vertex Clique Cover se puede reducir a su problema, y por lo tanto es NP-duro].

Lamentablemente, como se indica en la página de Wikipedia, el problema no puede aproximarse dentro de un $n^{1 - \varepsilon}$ y, por lo tanto, existe un algoritmo de aproximación polivalente que logra un factor razonable.

Si tienes conocimiento estructural del gráfico que estás estudiando, eso podría ayudar (por ejemplo, creo que si el grado está acotado, podrías aproximar algo).