Hace algún tiempo, publiqué una solicitud de referencia para problemas de gráficos en los que queremos encontrar una partición de 2 de los bordes donde ambos conjuntos cumplen una propiedad no relacionada con su cardinalidad. Estaba tratando de demostrar que el siguiente problema es NP-hard:
Dado un torneo , ¿hay un conjunto de arco de retroalimentación F ⊆ E en G que defina una relación transitiva?
Tengo una construcción para un intento de prueba, pero parece que eso va a toparse con un callejón sin salida, así que pensé en preguntar aquí para ver si me falta algo obvio. Para no limitar su creatividad a líneas de pensamiento similares a las que usé, no publicaré mi intento aquí.
¿Es este problema NP-hard? Si es así, ¿cómo probarlo?
np-hardness
reductions
G. Bach
fuente
fuente
Respuestas:
Para agregar un poco de contexto, aquí hay una construcción para un gráfico que no tiene un conjunto de arco de retroalimentación transitiva. Para esta construcción, usaré el siguiente gráfico de gadget:
Este torneo tiene las siguientes propiedades (que verifiqué usando un programa, no lo probé formalmente):
o ligeramente abusivo de la notación de lógica de predicado:
Notarás que para cada implicación, los dos bordes están separados por pares, por lo que la siguiente construcción funciona:
fuente
Ejecuté un programa corto de clingo que no informaba ningún gráfico sin un TFAS, pero había un error. Lo arreglé y ahora verifica que no hay gráfico sin un TFAS para n = 8 o menos. Para n = 9, encuentra este:
Aquí está la codificación (fija)
Ejecútelo con
clingo -c n=7 tfas.asp
(Uso de clingo 4.2.1)(n = 7 indica gráficas de exactamente 7 vértices)
Debería ser satisfactoria si y solo si existe un gráfico sin TFAS en 7 vértices.
Ok, descubrí qué gráfico @ G.Bach estaba describiendo y lo codifiqué en clingo (ver la descripción de clingo a continuación. Comienza con una descripción del gráfico del dispositivo y luego paso a describir cómo unir copias de él para obtener la información completa). Gráfico de torneo de 34 vértices que describe G.Bach. También he adjuntado la descripción del gráfico a tierra).
Luego procedí a ejecutar clingo en ese gráfico y afirmó haber encontrado un TFAS con 241 bordes. Pero cometí un error en la codificación del gráfico. Solucioné el error y ahora el clingo informa que no es satisfactorio (es decir, no hay TFAS).
Aquí está el programa para encontrar TFAS en un gráfico
Aquí está el programa (actualizado) para generar el gráfico de G.Bach. Agregué indicadores al final para verificar que el gráfico es un gráfico de torneo bien formado:
fuente
Conjetura SWAG [algo mejor que nada?]:
notas: ¡los contraejemplos de derribo son bienvenidos! ninguno parece haberse dado hasta ahora. incluso mejor serían algunas observaciones de patrones de orientaciones de bordes relacionadas con clases de gráficos particulares. o algo más de motivación o vincularlo a alguna literatura existente. ofrecido en el estilo de Pruebas y refutaciones (Lakatos) ... también, ya que parece un problema tan poco convencional que no se relaciona [todavía?], sugiera estudiarlo empíricamente ...
fuente