Par de ciclos de vértices disjuntos en un gráfico dirigido

13

¿Cuál es el algoritmo determinista más rápido conocido que puede reconocer gráficos dirigidos con un par de ciclos de vértices disjuntos? Sé que los gráficos con un mínimo de tres grados siempre tienen ese par ( Thomassen'83 ), pero aun así no puedo encontrar un algoritmo eficiente en el caso general. ¿Alguien sabe una referencia para esto?

reference-request Andreas Björklund
fuente
1
Para el gráfico no dirigido, es NP-completo reconocer gráficos con un conjunto de vértices divisible en dos ciclos de vértices separados de igual tamaño.
Mohammad Al-Turkistany
1
La caracterización de los gráficos no dirigidos tampoco es trival, debido a Lovasz, y se puede encontrar, por ejemplo, aquí: arxiv.org/abs/1601.03791 .
domotorp

Respuestas:

9

Según Grohe y Grüber " Aproximación parametrizada del problema del ciclo disjunto " (ICALP 2007) hay un algoritmo para encontrar ciclos de vértice-disjunto en un dígrafo, en el tiempo n f ( k ) para alguna función f (polinomio para k fijo pero no FPT) en la sección 5 de Reed, Robertson, Seymour y Thomas, " Empaquetado de circuitos dirigidos " (Combinatorica 1996) (que a su vez usa el teorema 3 de " El problema del hemeomorfismo del subgrafo dirigido " de Fortune, Hopcroft y Wyllie).knf(k)fk

David Eppstein
fuente
2
Solo quiero agregar un pequeño comentario. Puede valer la pena mirar el ancho de árbol dirigido y el reciente teorema de la cuadrícula de Kreutzer y Kawarabayashi que arroja algo de luz adicional sobre las técnicas en el papel de Reed et al. Eludieron el teorema menor de la cuadrícula dirigida para probar el teorema de Erdos-Posa para los gráficos dirigidos, pero es útil ver el esquema de alto nivel a la luz del teorema de la cuadrícula dirigida.
Chandra Chekuri el