Osiągalność (teoria grafów) – relacja dwuargumentowa między wierzchołkami danego grafu skierowanego. Niech G = (V, E) oznacza graf skierowany, gdzie V jest skończonym zbiorem wierzchołków, a E jest skończonym zbiorem krawędzi, czyli uporządkowanych par wierzchołków tego grafu. Wtedy relacja osiągalności zachodzi dla pary (x,y) (x,y ∊ V) wtedy i tylko wtedy, gdy istnieje ścieżka w grafie G prowadząca od wierzchołka x do wierzchołka y. Wówczas mówimy, że wierzchołek y jest osiągalny z wierzchołka x w grafie G.
Algorytmy Z relacją osiągalności wiąże się problem decyzyjny następującej postaci: mając daną trójkę (G, x, y), gdzie G jest grafem skierowanym (G = (V, E)) oraz x i y (x,y ∊ V) są wierzchołkami tego grafu, odpowiedzieć na pytanie, czy w grafie G wierzchołek y jest osiągalny z wierzchołka x. Wiadomo, że ten problem jest w klasie NL (znany jest algorytm o złożoności pamięciowej Ο(log(n)) dla niedeterministycznej maszyny Turinga).