Abstract:
The reachability problem for graphs cannot be described, in the sense of descriptive complexity theory, using a single first-order formula. This is true both for directed and undirected graphs, both in the finite and infinite. However, if we restrict ourselves to graphs in which a certain graph parameter is fixed to a certain value, first-order formulas often suffice. A trivial example are graphs whose number of vertices is fixed to $n$. In such graphs reachability can be described using a first-order formula with a quantifier nesting depth of $\log_2 n$, which is both a lower and an upper bound. In this paper we investigate how the descriptive complexity of the reachability problem varies as a function of graph parameters such as the size of the graph, the clique number, the matching number, the independence number or the domination number. The independence number turns out to be the by far most challenging graph parameter.