Ciclo hamiltoniano en gráficos sin ciclos pequeños

Mientras respondía esta pregunta en teoría , demostré (informalmente) sobre la marcha el siguiente teorema:

Teorema : para cualquier fija, la sonda del ciclo hamiltoniano permanece completa NP incluso si está restringida a gráficos bipartitos planos no direccionados de grado máximo 3 que no contienen ciclos de longitud . $l \geq 3$ $\leq l$

Parece muy poco probable que aún no haya aparecido en alguna parte.
Pero permite resolver muchos problemas de ciclo / ruta de Hamilton en graphclasses.org que están marcados como "Desconocidos para ISGCI" (ver, por ejemplo, este ); de hecho un corolario directo es que los problemas de ciclo y camino de Hamilton son todavía NP-completa si restringido a gráficos, donde cada uno de los contiene al menos un ciclo. $(H_1,...,H_k)\text{-free}$ $H_i$

¿Me puede dar una referencia del papel / libro donde apareció?

(luego me pondré en contacto con personas en graphclasses.org)

reference-request np-hardness Marzio De Biasi
fuente

Al menos estas discusiones ayudaron a obtener nuevos resultados en graphclasses.org, así que por favor informe a las clases gráficas sobre los resultados desconocidos para ellos: el enlace de contacto proporciona un formulario, la dirección de correo electrónico es opcional.

joro

@joro: ayer ya los contacté (también les di mi correo electrónico). Esperaré unos días y veré si actualizan el estado de esos problemas.

Marzio De Biasi

Escuché que no actualizan la base de datos muy a menudo y responden con "gracias" después de actualizar la base de datos y responden bastante bien.

joro

@joro: Creo que actualizaron la base de datos (son muy colaborativos y educados)

Marzio De Biasi

Respuestas:

El resultado se afirma en el artículo Dos nuevas clases de gráficos hamiltonianos de Arkin, Mitchell y Polinshchuk.

Kristoffer Arnsfelt Hansen
fuente

Este manuscrito inédito de Hougardy, Emden-Weinert y Kreuter en 1997 proporcionó una prueba simple para el siguiente resultado que es mucho más fuerte que el resultado señalado en la respuesta de Kristoffer Arnsfelt Hansen:

$0\le r <1/2$ $n$ $\ge n^r$

El manuscrito contiene también resultados similares para otros problemas, como el conjunto dominante, corte máximo, VFS, etc.

vb le
fuente

¡OK gracias! Olvidé mencionar que mi prueba funciona para gráficos bipartitos planos no direccionados de grado máximo 3 ... así que Hourgardy et al. el papel es más fuerte ... pero no mucho más fuerte :-) :-). Probablemente acepte la respuesta de Kristoffer porque la publicó primero.

Marzio De Biasi

@MarzioDeBiasi, creo que la fortaleza es del tamaño de una circunferencia. su prueba es sobre un número fijo, la respuesta aceptada es para alguna f (n) que es menor que sqrt y esta respuesta es más general que todas ellas. (La restricción de la OMI al gráfico no es muy importante aquí)

Saeed

El documento contiene otros problemas NP-hard, será una respuesta a la pregunta vinculada sobre gráficos cíclicos.

joro