Another measure for the lexicographically first maximal subgraph problems and its threshold value on a random graph
Ryuhei Uehara · 2003
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/sup k/ n) is in NC/sup k+1/, and the problem on a graph of LDPL /spl Theta/(n/sup /spl epsiv//) 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 and show that its threshold value is 1/n. This implies that a random graph of which each edge exists with probability p has LDPL /spl Theta/(np) with high probability. The result also show the limit of the LDPL on the average case.