tl; dr: Si está buscando copias inducidas de un gráfico de girasol, entonces creo que este es un problema computacionalmente difícil, porque los “pétalos” de un girasol inducen un conjunto independiente (según su definición), y parece como si pudiera reducir formalmente el conjunto independiente al problema de detectar un girasol , lo que automáticamente dificulta la versión de conteo / enumeración. Si no está buscando copias inducidas, entonces creo que puede mostrar que hay gráficos que contienen exponencialmente muchos gráficos de girasol, y me imagino que sería bastante complicado enumerarlos en tiempo polinómico.
Digamos que [matemáticas] H [/ matemáticas] es un girasol en C si es un girasol que consiste en el ciclo [matemáticas] C = \ {v_1, \ ldots, v_n \} [/ matemáticas] y “pétalos” [matemáticas ] \ {u_1, \ ldots, u_n \} [/ math]. Además, describamos el hecho de que [math] u_i [/ math] es adyacente a [math] v_i [/ math] y [math] v_ {i + 1} [/ math] diciendo que el borde [math] ( v_i, v_ {i + 1}) [/ math] tiene el pétalo [math] u_i [/ math]. (Creo que esta notación es ligeramente inconsistente con la suya; estoy usando [math] i + 1 [/ math] en lugar de [math] i-1 [/ math], pero es solo un cambio de nombre, ¡espero que sea soportable!)
Formulemos el siguiente problema más simple:
- ¿Cuál es la diferencia entre autómatas deterministas y no deterministas de estado finito?
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
- ¿Debo especializarme en informática teórica o aprendizaje automático?
- ¿Cuáles son algunos de los ejemplos más interesantes de problemas indecidibles sobre las máquinas de Turing?
- ¿Por qué 0 ^ 0 es igual a 1 en el estándar IEEE 754 aunque no tiene sentido?
Detección de girasol C: dado un gráfico [matemático] G = (V, E) [/ matemático], un subconjunto [matemático] C [/ matemático] de [matemático] G [/ matemático] tal que [matemático] C [/ matemática] induce un ciclo, ¿G tiene una subgrafía inducida H que es un girasol en [matemática] C [/ matemática]?
Hablando informalmente, si esperamos tener un algoritmo que enumere todos los girasoles inducidos en el tiempo polinómico, entonces deberíamos ser capaces de resolver, en particular, la pregunta anterior también en el tiempo polinómico. Sin embargo, creo que resulta que el problema que acabamos de describir (encontrar un girasol “encima” de un ciclo específico) ya es NP-hard, y describiré brevemente por qué.
Consideremos una instancia de Conjunto independiente multicolor (que es conocido por ser tan difícil como Independent Set):
Entrada: Una gráfica [matemática] G = (V, E) [/ matemática] y una partición de [matemática] V [/ matemática] en partes [matemática] k [/ matemática], [matemática] V_1, \ ldots, V_k [/mates].
Pregunta: ¿[math] G [/ math] tiene un conjunto independiente [math] S [/ math] tal que [math] | S \ cap V_i | = 1 [/ matemáticas] para todas [matemáticas] 1 \ leq i \ leq k [/ matemáticas]?
Ahora, aquí hay una reducción del conjunto independiente multicolor a la detección de girasol C. Considere la instancia [math] H [/ math] obtenida de [math] G [/ math] de la siguiente manera. Primero, agregamos un ciclo disjunto [matemática] C [/ matemática] en vértices [matemática] k [/ matemática], y dejamos que [matemática] C = \ {t_1, \ ldots, t_k \} [/ matemática], donde use [math] e_i [/ math] para denotar el borde [math] (t_i, t_ {i + 1}) [/ math]. Además, deje que [math] t_i [/ math] sea adyacente a todos los vértices en [math] V_i [/ math] y [math] V_ {i-1} [/ math] (módulo de índice k). Vea la imagen para un esquema informal (donde los dos vértices verdes son iguales).
Si [math] G [/ math] tiene un conjunto independiente multicolor [math] S: = (u_1, \ ldots, u_k) [/ math], observe que [math] H [/ math] tiene un girasol en [ matemática] C [/ matemática] simplemente eligiendo los vértices de [matemática] S [/ matemática] como los pétalos del ciclo base [matemática] C [/ matemática] – tenga en cuenta que [matemática] u_i [/ matemática] es adyacente a [math] t_i [/ math] y [math] t_ {i + 1} [/ math], por lo que es el pétalo del borde [math] e_i [/ math].
Por otro lado, suponga que [matemáticas] H [/ matemáticas] tiene un girasol en [matemáticas] C [/ matemáticas]. Considere el conjunto de pétalos para los bordes de [matemáticas] C [/ matemáticas]. El pétalo del borde [matemática] (v_i, v_ {i + 1}) [/ matemática] debe ser necesariamente un vértice de [matemática] V_i [/ matemática] (porque estos son los únicos vértices en [matemática] H [/ matemática] que tienen [math] v_i [/ math] y [math] v_ {i + 1} [/ math] como vecinos). Estos pétalos corresponden a un conjunto independiente multicolor en [matemática] G [/ matemática] porque la solución aquí fue un girasol inducido en [matemática] C [/ matemática].
Si desea girasoles que no sean necesariamente inducidos, entonces me temo que puede haber demasiados para enumerar en el tiempo polinómico. Por ejemplo, solo considere el gráfico completo en n vértices. Cualquier subgrafo de tamaño par contiene un girasol (en realidad muchos de ellos, si considera reelaboraciones), por lo que en general, un gráfico puede tener exponencialmente muchos girasoles. Creo que es poco probable que puedas enumerarlos en tiempo polinómico.
De hecho, contar ciclos ya es un problema muy difícil, incluso el problema de contar todos los ciclos hamiltonianos en un gráfico es # P completo (lo que significa que si encuentra un algoritmo de tiempo polinómico para este problema, entonces, entre otras cosas, P = NOTARIO PÚBLICO). El problema de contar los girasoles parece (muy vagamente) “contener” el problema de contar los ciclos, y me imagino que existe una reducción formal de la completitud # P entre los dos.
Esto nos deja con la cuestión de detectar un girasol que no necesariamente es inducido. Supongo que una posible intuición es que si no insiste en un girasol “inducido”, la parte de la dureza que proviene del conjunto independiente desaparece. Habiendo dicho eso, no puedo pensar en una respuesta fuera de mi cabeza 😐
Además, queda por demostrar que el problema de encontrar un girasol inducido con un ciclo base de longitud de al menos vértices [matemáticos] k [/ matemáticos] es NP-duro. Creo que la reducción descrita anteriormente se puede ajustar con algunos gadgets simples para mostrar esto también.
