A lower bound for the recognition of digraph properties (Q810043)

A digraph may be viewed as a subset of the edges on the node set. A collection of such digraphs is called a digraph property provided that it is invariant under renumbering of the nodes. The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case. It is shown that every digraph property which is monotone, being not distroyed by the deletion of edges, and nontrivial, being held for some but not all digraphs, has a lower bound of \(v^ 2/2-O(v^ 2)\) for its complexity, where v is the number of nodes in the digraph. In addition, it is shown that a certain class of monotone, nontrivial bipartite digraph properties is evasive, requiring that every entry in the adjacency matrix be examined in the worst case.