Recolorear gráficos bipartitos

Dado un gráfico bipartito donde cada vértice está coloreado de rojo o azul, estoy tratando de minimizar el número de vértices azules usando la siguiente operación:$G = (A,B,E)$

1. Elija un vértice en$v_a$$A$
2. Voltee los colores de , lo que significa que y todos los vecinos de cambiarán de color.$N[v_a]$$v_a$$v_a$

¿Existe un algoritmo de tiempo polinómico para seleccionar un conjunto de recoloración que minimice la cantidad de vértices azules? El número de coloraciones necesarias no es relevante.$X \subseteq A$

Observe que el orden de volteo no importa, y por cada vértice en , lo voltea o no. Podemos pensar en los colores como un número que se incrementa en el módulo 2. Esto produce un algoritmo trivial .$A$$O(2^{|A|} \cdot n)$

El problema es NP-completo y, por lo tanto, no es probable que admita un algoritmo de tiempo polinómico. A continuación se muestra una prueba de la completitud NP del problema, que se muestra mediante una reducción de 1 en 3 SAT.

Sea una instancia de 1-IN-3-SAT, donde se nos da una fórmula 3-CNF-SAT para encontrar una asignación satisfactoria donde cada cláusula se satisface exactamente con un literal. Sea el conjunto de variables y el conjunto de cláusulas.$\phi$$V(\phi)$$n$$C(\phi)$$m$

Construimos una instancia con un presupuesto de (el número permitido de vértices azules).$G = (A,B,E)$$b = n + m$

Para cada variable , construya dos vértices rojos y en junto con vértices azules en adyacentes a ambos. Esto obliga a exactamente uno de o . También terminamos con "vértices variables" invertidos, utilizando así la primera parte del presupuesto.$x \in V(\phi)$$v_x$$v_{\overline{x}}$$A$$b+1$$B$$v_x$$v_{\overline{x}}$$n$

Observación: son los únicos vértices en .$\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$$A$

Para cada cláusula, digamos , creamos vértices azules y tres vértices rojos adicionales , todos en . Deje que estén completamente adyacentes a los vértices azules y conecte a , a , y a .$c = x \lor \overline{y} \lor z$$b+1$$v_{x \in c},v_{\overline{y} \in c},v_{z \in c}$$B$$v_x,v_{\overline{y}},v_z$$b+1$$v_x$$v_{x \in c}$$v_y$$v_{\overline{y} \in c}$$v_z$$v_{z \in c}$

Ahora, dado que cada gadget de cláusula tiene vértices azules , sabemos que se han invertido uno o tres literales en esa cláusula. Supongamos que tres se voltearon por una de las cláusulas. Pero luego usamos al menos el presupuesto .$b+1$$n + m + 2$

Supongamos que es una instancia de sí con una asignación 1 en 3 . Voltea cada vértice que corresponde a . Como cada cláusula se satisface con exactamente una variable, para cada cláusula ahora hay un vértice azul, y para cada variable, exactamente una de ellas es azul, por lo tanto tenemos vértices azules.$\phi$$\alpha: V(\phi) \to \{\top,\bot\}$$\alpha$$n + m = b$

Pål GD explica que el problema es NP-hard, por lo que el siguiente paso es tratar de encontrar algoritmos razonables para su problema.

Notaré que su problema puede reducirse a CÓDIGO DE PESO MÍNIMO: dado un código lineal, busque una palabra de código de peso mínimo. Otra forma de plantear este problema es: dada una matriz booleana y un vector booleano , encuentre un vector booleano no cero tal que el peso de Hamming de se minimice. (Toda la aritmética se realiza en el módulo 2). Se sabe que la CODEWORD DE PESO MÍNIMO es NP-hard, pero hay algunos algoritmos que son más rápidos que la fuerza bruta.$M$$y$$x$$Mx \oplus y$

Aquí está la conexión. Si hay vértices, puede pensarse que cualquier vector booleano de bits especifica qué vértices se voltearán mediante una operación de volteo particular. Por lo tanto, para cada vértice obtenemos un vector flip correspondiente . Póngalos en una matriz , donde cada fila corresponde a un flip-vector diferente. Sea un vector booleano de bits que especifica los colores originales de los vértices (azul = 1, rojo = 0). Ahora el objetivo es encontrar un vector booleano que minimice el peso de Hamming de$n$$n$$v$$m_v$$n \times n$$y$$n$$x$$Mv \oplus y$. Cualquiera de estos vectores corresponde inmediatamente a un conjunto de operaciones de volteo que minimiza el número de vértices azules en el gráfico.

Con estos antecedentes, es posible que pueda aplicar a su problema algoritmos conocidos para encontrar palabras de código de peso mínimo en códigos lineales. El tiempo de ejecución seguirá siendo exponencial, pero más rápido que probar todas las posibilidades para . $x$