__
TR06-035 | 19th January 2006 00:00
__

#### The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

**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.