# Lower Bounds on the Lengths of Node Sequences in Directed Graphs

## Abstract

A strong node sequence for a directed graph *G=(N,A)* is a sequence of nodes containing every cycle-free path of *G* as a subsequence. A weak node sequence for *G* is a sequence of nodes containing every basic path in *G* as a subsequence, where a basic path *n _{1}, n_{2}, ..., n_{k}* is a path from

*n1*to

*n*such that no proper subsequence is a path from

_{k}*n*to

_{1}*n*. (Every strong node sequence for

_{k}*G*is a weak node sequence for

*G*.) Kennedy has developed a global program data flow analysis method using node sequences. Kwiatowski and Kleitman have shown that any strong node sequence for the complete graph on

*n*nodes must have length at least

*n*

^{2}-O(

*n*

^{7/4+α}), for arbitrary positive ε. Every graph on

*n*nodes has a strong sequence of length

*n*+4, so this bound is tight to within O(

^{2}-2n*n*

^{7/4+α}). However, the complete graph on n nodes has a weak node sequence of length

*n*nodes (all with in-degree and out-degree bounded by two) such that any weak node sequence for

*G*has length at least 1/2 log

_{2}

*n*-O(

*n*log log

*n*). Aho and Ullman have shown that every reducible flow graph has a strong node sequence of length O(

*n*log

_{2 n}); thus our bound is tight to within a constant factor for reducible graphs. We also show that for infinitely many

*n*, there is a (non-reducible) flow graph

*H*with

*n*nodes (all with in-degree and out-degree bounded by two), such that any weak node sequence for

*H*has length at least

*cn*, where

^{2}*c*is a positive constant. This bound, too, is tight to within a constant factor.

## Recommended Citation

G.
Markowsky
and
R.
E.
Tarjan,
"Lower Bounds on the Lengths of Node Sequences in Directed Graphs," *Discrete Mathematics*, vol. 16, no. 4, pp. 329 - 337, Elsevier, Dec 1976.

The definitive version is available at https://doi.org/10.1016/S0012-365X(76)80007-6

## Department(s)

Computer Science

## International Standard Serial Number (ISSN)

0012-365X

## Document Type

Article - Journal

## Document Version

Citation

## File Type

text

## Language(s)

English

## Rights

© 1976 Elsevier, All rights reserved.

## Publication Date

01 Dec 1976