Abstract
We investigate structural parameters of a graph that express the boundary of the parallel complexity of the lexicographically first maximal independent set (LFMIS) problem. As a measure, we introduce the longest directed path length (LDPL). That is better than previously known one. The parallel complexity of the LFMIS problem on a graph gradually increases as the value measured on the graph grows: The LFMIS problem on a graph of LDPL O(\log^k n) is in NC^{k+1}, and the problem on a graph of LDPL \Theta(n^{\epsilon}) is P-complete.We also investigate the limit of the measure. We construct a kind of the lexicographically first maximal subgraph problems such that the problem is P-complete even if the LDPL of the input graph is restricted to 1.Finally we discuss the probability that a random graph has LDPL l and show that its threshold value is l/n. This implies that a random graph of which each edge exists with probability p has LDPL \Theta(np) with high probability. The result also show the limit of the LDPL on the average case.