Conjunto de arco de retroalimentación transitiva (TFAS): NP-complete?

13

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?sol=(V,mi)Fmisol

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?

G. Bach
fuente
1
¡perfecto gracias! (Eliminé el comentario porque escribí G = (E, V) en lugar del estándar G = (V, E) :-)
Marzio De Biasi
66
Si entiendo correctamente, esto es equivalente a preguntar si los bordes de un torneo se pueden dividir en dos DAG, uno de los cuales está cerrado transitivamente.
dspyz
1
Según el comentario de dspyz, no hay tantos problemas en los DAG que puedan estudiarse debido a su complejidad. ni siquiera parece que haya muchos teoremas sobre los DAG. Los árboles son un poco más accesibles. su problema (aunque aparentemente interesante como se refleja en los votos) parece mezclar muchos elementos inusuales y no encajar en ninguna categoría en particular.
vzn
55
@IgorShinkar los arcos de cualquier dígrafo se pueden dividir trivialmente en dos DAG: ordenar los vértices arbitrariamente; un DAG son los bordes delanteros, el otro DAG son los bordes hacia atrás.
Sasho Nikolov
1
@SashoNikolov, por supuesto!
Igor Shinkar

Respuestas:

4

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:

gráfico de dispositivo utilizado para forzar implicaciones

Este torneo tiene las siguientes propiedades (que verifiqué usando un programa, no lo probé formalmente):

  • si (2,7) no está en un TFAS dado, entonces (1,3) es
  • si (5,1) está en un TFAS dado, entonces también lo está (3,6)
  • si (7,3) está en un TFAS dado, entonces (5,1) no está

o ligeramente abusivo de la notación de lógica de predicado:

  • ¬(2,7 7)(1,3)
  • (5 5,1)(3,6 6)
  • (7 7,3)¬(5 5,1)

Notarás que para cada implicación, los dos bordes están separados por pares, por lo que la siguiente construcción funciona:

construcción para gráfico que no tiene TFAS

UN

G. Bach
fuente
Lo siento, no te sigo. ¿Hay alguna razón por la que no pueda simplemente publicar una lista de los bordes para que pueda ejecutarlo a través de un solucionador ASP e intentar verificarlo? Según clingo, su gráfico de gadget tiene 8 TFAS diferentes. Aquí está el más pequeño: tfas (borde (5,0)) tfas (borde (6,0)) tfas (borde (7,0)) tfas (borde (6,2)) tfas (borde (7,3)) tfas (edge ​​(1,2)) tfas (edge ​​(1,3)) tfas (edge ​​(7,5))
dspyz
Acabo de notar que mencionaste el borde (6,3) en el gráfico del gadget, pero la imagen que proporcionaste tiene el borde (3,6)
dspyz
Lo descubrí, vea mi respuesta actualizada: cstheory.stackexchange.com/a/20778/13643
dspyz
@dspyz Pensé que la construcción era más clara que solo una lista de los bordes, ya que si mi razonamiento no es incorrecto, todo lo que se requeriría para verificar es si el torneo sobre la construcción realmente tiene esas propiedades de implicación. ¡Gracias por señalar el error sobre edge (3,6)! También obtuve 8 TFAS para ese gadget, el que mencionaste como uno de ellos.
G. Bach
Lo siento. Construí mal el gráfico. Lo arreglé y clingo ahora informa que no hay TFAS.
dspyz
1

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:

is_edge(edge(2,3)) is_edge(edge(1,4)) is_edge(edge(2,4)) is_edge(edge(3,5)) is_edge(edge(4,5)) is_edge(edge(1,6)) is_edge(edge(2,6)) is_edge(edge(3,6)) is_edge(edge(5,6)) is_edge(edge(1,7)) is_edge(edge(4,7)) is_edge(edge(5,7)) is_edge(edge(6,7)) is_edge(edge(1,8)) is_edge(edge(3,8)) is_edge(edge(4,8)) is_edge(edge(5,9)) is_edge(edge(6,9)) is_edge(edge(7,9)) is_edge(edge(2,1)) is_edge(edge(3,1)) is_edge(edge(4,3)) is_edge(edge(5,1)) is_edge(edge(5,2)) is_edge(edge(6,4)) is_edge(edge(7,2)) is_edge(edge(7,3)) is_edge(edge(8,2)) is_edge(edge(8,5)) is_edge(edge(8,6)) is_edge(edge(8,7)) is_edge(edge(9,1)) is_edge(edge(9,2)) is_edge(edge(9,3)) is_edge(edge(9,4)) is_edge(edge(9,8))

Aquí está la codificación (fija)

% tfas.asp
#show is_edge/1.
vertex(1..n).

opp_edges(edge(A,B),edge(B,A)) :- vertex(A), vertex(B), A < B.
possible_edge(E1;E2) :- opp_edges(E1,E2).

{is_edge(E1); is_edge(E2)} = 1 :- opp_edges(E1, E2).
ntfas(E) :- possible_edge(E), not is_edge(E).
ntfas(edge(X, X)) :- vertex(X).

tfas(E) | fs(E) :- is_edge(E).
ntfas(E) :- fs(E).

broken :- ntfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- fs(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), fs(edge(Y, Z)), is_edge(edge(Y, Z)).
broken :- reachable(X, X).

tfas(E) :- broken, possible_edge(E).
fs(E) :- broken, possible_edge(E).
:- not broken.

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

{tfas(E)} :- is_edge(E).
:- not tfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- not tfas(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), not tfas(edge(Y, Z)), is_edge(edge(Y, Z)).
:- reachable(X, X).

tfas_count(N) :- N = #count{tfas(E) : tfas(E)}.

#show tfas/1.
#show tfas_count/1.

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:

gadget_vertex(0..7).

gadget_edge(0,1).
gadget_edge(0,2).
gadget_edge(0,3).
gadget_edge(0,4).
gadget_edge(1,2).
gadget_edge(1,3).
gadget_edge(1,6).
gadget_edge(1,7).
gadget_edge(2,3).
gadget_edge(2,4).
gadget_edge(2,5).
gadget_edge(2,7).
gadget_edge(3,4).
gadget_edge(3,5).
gadget_edge(3,6).
gadget_edge(4,1).
gadget_edge(4,5).
gadget_edge(4,6).
gadget_edge(4,7).
gadget_edge(5,0).
gadget_edge(5,1).
gadget_edge(5,6).
gadget_edge(6,0).
gadget_edge(6,2).
gadget_edge(6,7).
gadget_edge(7,0).
gadget_edge(7,3).
gadget_edge(7,5).

special_edge(a;b;c;d;e).

forces(a,b).
forces(b,c).
forcesn(c,a).
nforces(a,d).
forces(d,e).
forces(e,a).

relates(A,B) :- forces(A,B).
relates(A,B) :- nforces(A,B).
relates(A,B) :- forcesn(A,B).

is_se_pair(se_pair(A,B)) :- relates(A,B).
vertex_name(v(V,P)) :- gadget_vertex(V), is_se_pair(P).

matches(from(A), v(5, se_pair(A,B))) :- forces(A,B).
matches(to(A), v(1, se_pair(A,B))) :- forces(A,B).
matches(from(B), v(3, se_pair(A,B))) :- forces(A,B).
matches(to(B), v(6, se_pair(A,B))) :- forces(A,B).

matches(from(A), v(2, se_pair(A,B))) :- nforces(A,B).
matches(to(A), v(7, se_pair(A,B))) :- nforces(A,B).
matches(from(B), v(1, se_pair(A,B))) :- nforces(A,B).
matches(to(B), v(3, se_pair(A,B))) :- nforces(A,B).

matches(from(A), v(7, se_pair(A,B))) :- forcesn(A,B).
matches(to(A), v(3, se_pair(A,B))) :- forcesn(A,B).
matches(from(B), v(5, se_pair(A,B))) :- forcesn(A,B).
matches(to(B), v(1, se_pair(A,B))) :- forcesn(A,B).

same_vertex(V, V) :- vertex_name(V).
same_vertex(M, N; N, M) :- matches(X, M), matches(X, N).

already_found(v(Y,N2)) :- vertex_name(v(X,N1)), same_vertex(v(X,N1),v(Y,N2)), N1 < N2.
vertex(V) :- vertex_name(V), not already_found(V).

named_gadget_edge(edge(v(X,SE),v(Y,SE))) :- gadget_edge(X,Y), is_se_pair(SE).
from_gadget_edge_named(edge(A, B), edge(C,D)) :- named_gadget_edge(edge(C,D)), same_vertex(A,C), same_vertex(B,D), vertex(A), vertex(B).
from_gadget_edge(edge(A,B)) :- from_gadget_edge_named(edge(A,B),edge(C,D)).
is_edge(E) :- from_gadget_edge(E).
is_edge(edge(A,B)) :- vertex(A), vertex(B), A < B, not from_gadget_edge(edge(B,A)).

vertex_count(VN) :- VN = #count{vertex(V) : vertex(V)}.
edge_count(EN) :- EN = #count{is_edge(E) : is_edge(E)}.

#show vertex_count/1.
#show edge_count/1.

bidirectional :- is_edge(edge(A,B)), is_edge(edge(B,A)).
phantom_vertex :- is_edge(edge(A,B)), not vertex(A).
phantom_vertex :- is_edge(edge(A,B)), not vertex(B).
incomplete :- vertex(A), vertex(B), not is_edge(edge(A,B)), not is_edge(edge(B,A)), A != B.

#show bidirectional/0.
#show phantom_vertex/0.
#show incomplete/0.
dspyz
fuente
Estoy seguro de que hay un torneo en 18 vértices que no tiene un TFAS.
G. Bach
¿Puedes por favor darlo como ejemplo? Simplemente adjunte un archivo con los bordes enumerados
dspyz
¿Cómo adjunto un archivo? Puede tomar algunas horas, no tengo el torneo a mano en este momento. También calculé mal, debería tener 34 vértices. Probablemente sea más fácil verificar si doy los componentes básicos del torneo.
G. Bach
Cargue en cualquier host de archivos y enlace a él (vea meta.stackexchange.com/a/4643/185877 ), o si tiene una estructura regular, solo descríbalo (dé los bloques de construcción)
dspyz
¿No puede seguir su código todavía pero está afirmando que está validando para nite20 finito? última oración que afirma que es cierto para todosnorte... si es tan notable (!) pero no es una "solución" a la pregunta general (que requeriría una prueba de todos los casos de tamaño). ps gracias por trabajar / publicar una observación empírica en este sitio, lo que en general es raro ... @ G.Bach sería genial ver una imagen del gráfico en lugar de solo listas de bordes / vértices si es posible
vzn
0

Conjetura SWAG [algo mejor que nada?]:

Dado un torneo sol=(V,mi), existe un conjunto de arco de retroalimentación Fmi en soleso define una relación transitiva. por eso el problema esO(1)

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 ...

vzn
fuente
1
Ejecuté un programa para verificar si esto funciona y descubrí que hay torneos que no tienen un arco de retroalimentación transitiva. Publicaré uno mañana, no voy a hacerlo hoy.
G. Bach
@vzn, ¿puedes probar la conjetura de un torneo aleatorio?
Igor Shinkar
Contraejemplo con solo 5 vértices: a-> b, a-> c, b-> c, d-> a, b-> d, c-> d, e-> a, e-> b, c-> e , d-> e. Para cualquiera de los cuatro vértices, el gráfico inducido contiene un ciclo, por lo que un DAG transitivo puede contener como máximo 3 bordes entre 3 vértices del gráfico. Solo hay 5 posibilidades (todos los otros trillizos son ciclos): abc, eab, dea, bcd, cde Es fácil verificar que en cada uno de los cinco casos hay un ciclo entre los otros 7 bordes
dspyz
1
Sí, no importa, no es un contraejemplo
dspyz
1
@dspyz Realicé una verificación de fuerza bruta en todos los torneos en hasta 8 vértices. Todos ellos tienen conjuntos de arco de retroalimentación transitiva, pero hay algunos que puedes usar para construir un torneo que no.
G. Bach