Zmienna w CSP jest spójna łukowo, jeśli każda wartość w jej domenie spełnia ograniczenia binarne zmiennej. Bardziej formalnie Xi, jest łukowo spójne w odniesieniu do innej zmiennej Xj, jeśli dla każdej wartości w bieżącej dziedzinie Di istnieje jakaś wartość w dziedzinie Dj, która spełnia binarne ograniczenie łuku (Xi, Xj). Wykres jest zgodny łukowo, jeśli każda zmienna jest spójna łukowo z każdą inną zmienną. Rozważmy na przykład ograniczenie Y = X2, gdzie domena obu i jest zbiorem cyfr dziesiętnych. Możemy napisać to ograniczenie jawnie jako
Aby łuk X był spójny względem , zmniejszamy dziedzinę X do {0,1,2,3} . Jeśli uczynimy arcus-spójny również względem , wtedy domeną , {0,1,4,9} i cały CSP jest arcus-spójny. Z drugiej strony, spójność łuku nie może nic zrobić dla Australii z problemem z kolorowaniem mapy. Rozważ następujące ograniczenie nierówności na (SA,WA):
Bez względu na to, jaką wartość wybierzesz dla SA (lub dla WA ), istnieje prawidłowa wartość dla drugiej zmiennej. Zatem stosowanie spójności łuku nie ma wpływu na domeny żadnej ze zmiennych. Najpopularniejszy algorytm wymuszania spójności łuku nazywa się AC-3 (patrz Rysunek 6.3 ). Aby każda zmienna była spójna, algorytm AC-3 utrzymuje kolejkę łuków do rozważenia. Początkowo kolejka zawiera wszystkie łuki w CSP. (Każde ograniczenie binarne staje się dwoma łukami, po jednym w każdym kierunku.) AC-3 następnie zdejmuje dowolny łuk (Xi,Xj) z kolejki i czyni łuk Xi spójnym względem . Jeśli to pozostawia Di bez zmian, algorytm po prostu przechodzi do następnego łuku. Ale jeśli to zrewiduje Di (zmniejszy domenę), to dodamy do kolejki wszystkie łuki (Xk,Xi), gdzie Xk jest sąsiadem Xi . Musimy to zrobić, ponieważ zmiana w D1 może umożliwić dalsze redukcje Dk , nawet jeśli wcześniej braliśmy pod uwagę Xk. Jeśli Di zostanie zrewidowany do zera, to wiemy, że cały CSP nie ma spójnego rozwiązania, a AC-3 może natychmiast zwrócić niepowodzenie. W przeciwnym razie sprawdzamy, próbując usunąć wartości z domen zmiennych, aż w kolejce nie będzie już żadnych łuków. W tym momencie zostajemy z CSP, który jest równoważny oryginalnemu CSP — oba mają takie same rozwiązania — ale CSP o spójnym łuku będzie szybciej wyszukiwany, ponieważ jego zmienne mają mniejsze domeny. W niektórych przypadkach całkowicie rozwiązuje problem (redukując każdą domenę do rozmiaru 1), a w innych dowodzi, że nie ma rozwiązania (redukując pewną domenę do rozmiaru 0).
Złożoność AC-3 można przeanalizować w następujący sposób. Załóżmy, że dostawca CSP ma n zmiennych, z których każda ma najwyżej rozmiar domeny i ograniczenia binarne (łuki). Każdy łuk (Xk,Xi) może być wstawiony do kolejki tylko raz, ponieważ Xi ma co najwyżej wartości do usunięcia. Sprawdzenie spójności łuku można wykonać w czasie O(d2), więc otrzymujemy całkowity czas najgorszego przypadku O(cd3).