Algoritmo SAT per determinare se un grafico è disgiunta

Question

Quali sono alcuni buoni algoritmi per avere un risolutore SAT (CNF) che determinano se un determinato grafico è completamente connesso o disgiunta?

Il migliore a cui riesco a pensare è questo:

• Numero i nodi 1..n, dove n è il numero di nodi nel grafico.
• Definire le variabili N^2 con la coppia ordinata (p, q), dove p = 1..n e q = 0..n-1.
• SET (1,0) su True.
• Impostare (a, p+1) su vero IFF c'è un bordo che collega il nodo A e il nodo B e (b, p) è vero.
• Se esiste una variabile vera (x, y) per tutti i possibili nodi x, il grafico è collegato.

In effetti, (x, y) significa "Il nodo x è Y passi lontano dal nodo x".

Questo sembra inefficiente nelle variabili O (n^2). Può essere migliorato?

Un commento (da quando ho pubblicato questo su cstheory.stackexchange.com) mi ha chiesto perché avrei avuto bisogno di un algoritmo basato su SAT quando gli algoritmi O (N) per la connettività sono ben noti. Il motivo è semplice: ho molti altri vincoli basati su SAT sul grafico che devono anche essere soddisfatti allo stesso tempo.