Resolver Exact2IS usando es

Question

Me encontré con el siguiente problema:

exact2is= {g tiene exactamente 2 conjuntos independientes}

Suponiendo que se le dio un gráfico G Puedo encontrar un conjunto independiente ¿Cómo puedo verificar si G tiene exactamente 2 conjuntos independientes?

(puedo verificar si un gráfico contiene un conjunto independiente en O (1) y también encontrar un conjunto independiente en O (1))

Estaba pensando en encontrar un conjunto independiente (si existe) de Tamaño K y luego retirar un vértice del conjunto y verifique si el gráfico todavía tiene un conjunto independiente de tamaño k -Espués de ver, devolveré el vértice al gráfico exactamente como lo fue.

El problema Mi idea Revisa solo si un gráfico G contiene al menos 2 conjuntos independientes y no exactamente.

Cualquier persona tiene una idea ¿Cómo puedo verificar si una gráfica tiene exactamente 2 conjuntos independientes (en tiempo de polinomio y se le da el hecho de que encuentre y verifique si hay un conjunto independiente es O (1))?

Se apreciarán las pistas o ideas :) Gracias

Answer 1

En primer lugar, si puede determinar si un gráfico $ g $ contiene un conjunto independiente de tamaño $ k $ , entonces también puede encontrar dicho conjunto de manera eficiente. Esto se conoce como "reducción de búsqueda a la decisión". Aquí está la idea básica. Elija un vértice arbitrario $ v $ y elimínelo. Si la gráfica todavía tiene un conjunto independiente de tamaño $ k $ , luego sigue adelante. De lo contrario, todos los conjuntos independientes de tamaño $ k $ contienen $ v $ . En consecuencia, elimine $ v $ y a todos sus vecinos, y encuentre un conjunto independiente de tamaño $ k-1 $ En el gráfico restante. De esta manera, puede recuperar un conjunto independiente de tamaño $ k $ .

segundo, cómo verificar si un gráfico contiene al menos dos conjuntos independientes de tamaño $ k $ , asumiendo $ k \ geq 2 $ . Primero, usted determina si contiene al menos uno. Supongamos que lo hace, digamos $ i $ . Si $ j $ es cualquier otro conjunto independiente, luego $ i \ setminus j $ y $ j \ setminus i $ son ambos no vacíos (desde $ | i |= | j | j | $ ). En particular, si $ x \ en i \ setminus j $ y $ y $ es cualquier otro vértice en $ i $ , incluso después de agregar el borde $ (x, y) $ , el conjunto $ J $ constituirá un conjunto independiente.

Esto conduce al siguiente algoritmo: para cada par de vértices $ x, y \ in i $ , verifique si $ G + (x, y) $ contiene un conjunto independiente de tamaño $ k $ . Si es así, este conjunto independiente es necesariamente diferente de $ i $ . A la inversa, si un conjunto independiente de tamaño $ k $ diferente a $ i $ existe, entonces es necesariamente Sea un conjunto independiente en $ g + (x, y) $ para algunos $ x, y \ in i $ .

tercero, cómo verificar si una gráfica contiene exactamente dos conjuntos independientes de tamaño $ k $ . Esto es lo mismo que verificar si una gráfica contiene al menos tres conjuntos independientes de tres . Creo que en este punto, es mejor si intentas generalizar el argumento anterior de dos a tres conjuntos independientes. Podrías quedar atrapado, pero no lo sabrás hasta que lo intentes.

Answer 2

Si se le permite encontrar an de talla $ k $ en $ \Mathcal O (1) $ , entonces lo que ha escrito es casi la solución.Solo encuentre dos veces un tamaño de tamaño $ k $ , y después de ese cheque para ver si todavía hay otro.

Pero, por lo general, para las máquinas de Oracle, no se le permite encontrar un (en este ejemplo) está dentro de $ \ mathcal o (1) $ tiempo, y ustedSolo se les permite verificar ver si uno existe dentro de $ \ mathcal o (1) $ .

¡Espero que esto ayude!