Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-035 | 19th January 2006 00:00

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


Authors: Till Tantau
Publication: 13th March 2006 10:29
Downloads: 1137


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.

ISSN 1433-8092 | Imprint