Quand une propriété FO élimine-t-elle la dureté NL?

10

Contexte: Nous considérons uniquement les digraphes. Soit CYCLE le langage des graphes avec un cycle; c'est un problème NL-complet. Soit HASEDGE le langage des graphiques avec au moins un bord. Ensuite, trivialement, n'est plus NL-hard, tandis que reste.CYCLEHASEDGECYCLEHASEDGE¯

Problème réel: je me demande si la langue est toujours NL-difficile.

CYCLE{(V,E):(u,v,x,y)[E(u,v)E(x,y)¬E(u,y)¬E(x,v)]}

Question: Pour quelle formule FO sur le vocabulaire des graphiques est NL-hard? Cette propriété est-elle décidable?ϕ

CYCLE{(V,E):(V,E)ϕ}

Merci pour votre contribution!

Michaël Cadilhac
la source

Réponses:

4

Permettez-moi d'appeler la propriété dans votre "Problème réel" . Le mappage suivant réduit à :NODIAGCYCLECYCLENODIAG

Pour un , remplacer chaque sommet dans par deux copies et , et s'il y a une arête dans , soit avoir des arêtes et . Ainsi pour tout le graphe satisfait .G=(V,E)vGvv(u,v)EG(u,v),(u,v),(u,v)(u,v)GG¬NODIAG

De plus, a un cycle ssi a un cycle, donc satisfait ssi satisfait . Par conséquent, est NL-hard.GGGCYCLENODIAGGCYCLECYCLENODIAG

Je pense qu'une construction similaire fonctionnerait pour chaque propriété purement universelle.

Jan Johannsen
la source
Merci pour votre travail Jan! Mais je ne suis pas sûr que vous ayez résolu le problème complètement, car si une structure NODIAG apparaît en G, elle apparaît toujours à la fin de votre construction, AFAIU.
Michaël Cadilhac
Oui, mais alors quoi. La construction impose que . Donc, si , alors , donc . OTOH, si , alors , et donc . Ainsi, la construction réduit à . G¬NODIAGGCYCLEGCYCLEGCYCLENODIAGGCYCLEGCYCLEGCYCLENODIAGCYCLECYCLENODIAG
Jan Johannsen
Jan, je suis profondément désolé, j'ai foiré le libellé de ma question; le sous-graphique décrit devait être considéré comme un graphique EXCLU. Notez qu'avec la formulation précédente, il vous suffirait d'ajouter quatre nouveaux nœuds et arêtes , et pour que le graphique soit hors de NODIAG. Encore une fois, je suis vraiment désolé pour les fautes de frappe. u,v,x,yuvxyuy
Michaël Cadilhac
(PS: comme je vous le dois pour avoir travaillé sur une question erronée, voici un article TCS avec un joli titre qui n'apparaît pas dans votre liste: Diamonds are Forever (The Variety DA) de Tesson et Therien.)
Michaël Cadilhac
Dans ce cas, que diriez-vous d'ajouter simplement un nouveau sommet dans chaque arête: dans remplacez chaque par et . Le graphe résultant est cyclique si est, et n'a pas la structure exclue. BTW Je ne maintiens plus cette liste. Ge=(u,v)(u,ve)(ve,v)GG
Jan Johannsen
2

Le vrai problème est dans FO. Tester s'il existe telle sorte que et est évidemment dans FO.a,b,c,dV(G)(a,c),(b,d)E(G)(a,d),(b,c)E(G)

Supposons qu'il n'y ait pas de tels , alors admet un cycle dirigé si et seulement si admet un cycle dirigé de longueur deux. Cela peut être déduit du fait que pour deux sommets et quelconques de , leurs voisinages et sont tels que ou .a,b,c,dGGabGN(a)N(b)N(a)N(b)N(b)N(a)

Ainsi, il suffit de vérifier s'il existe tel que , qui est dans FO.a,bV(G)(a,b),(b,a)E(G)

Donc, est dans si et seulement siGCYCLENODIAG(a,b,c,d)[(E(a,b)E(c,d)¬E(a,d)¬E(b,c))(E(a,b)E(b,a))]

Adrien
la source
Merci Adrien. Pourriez-vous ajouter un argument expliquant pourquoi les quartiers extérieurs de deux nœuds sont comparables? J'attendrai un peu pour voir si quelqu'un aborde le problème complet, et si personne ne se présente, je vais chercher votre réponse.
Michaël Cadilhac
Je ne pense pas que la comparabilité des quartiers extérieurs soit réelle. Prenons par exemple le graphique de seulement quatre sommets avec des arêtes et . Ce graphique satisfait la formule de Michael, mais est incomparable avec . a,b,c,d(a,c)(b,d)N(a)={c}N(b)={d}
Jan Johannsen du
@Jan: Si je ne me trompe pas, le point d'Adrien est que si un graphique <i> ne </i> satisfait pas la deuxième partie, alors s'il a un cycle, il a un cycle de longueur 2. Donc, son point est que si le graphique <i> ne </i> satisfait pas la deuxième partie, alors la comparabilité est vraie.
Michaël Cadilhac