On Parallelizability of α-Connectivity

概要

論文の詳細を見る
Consider the common algorithm obtaining connected components of undirected graphs. As some connected component U grows, a nearby vertex νis absorbed into U if νis connected to U, i.e.,if an edge exists between νand some vertex in U. An obvious problem in this connectivity is that it does not reflect the strength of the connection. This naturally leads us to another graph connectivity which we call α-connectivity. Unlike the conventional connectivity,α-connectivity requires that the vertex νshould have at least ⌈d(ν)・α/n⌉neighbors in U, where d(ν)denotes the degree of vertex ν.(Suppose for example that n=100and α=10.Then νcan join U only if at least one tenth of ν's neighbors are included in U.)One can imagine the force of gravity between a star and a meteorite and a certain kind of clustering problems for its application. When α=1,α-connectivity is the same as the conventional connectivity. In this paper, we discuss the parallel complexity of this α-connectivity problem (obtaining α-connected components).Our result is remarkable in that the complexity gradually increases as the value of αgrows:(i)α-connectivity is in NC^t when α=c<(log n)>^<<t-2>/2>for positive constants c and t ≥2.(ii) The complexity jumps if the value αbecomes a bit larger: It is P-complete when αis given by two positive constants c and (any small)εas α=cn^ε.In the field of P and NP,"gradually intractable problems" whose complexity changes from P to NP-complete are not rare. Most problems prefixed by "k-",such as k-clique, fall into this category. However,"gradually unparallelizable problems" are rare. As the gradually intractable problems nicely exhibit fundamental differences between P and NP-complete,α-connectivity is expected to play the same role inside P. Obviously, k-connectivity, which is also a generalization of graph connectivity, is related to our α-connectivity. shows that k-connectivity can be solved in O(k^2 log n) time by a polynomial number of processors. Thus the bound continuously grows with k as α-connectivity, but it is open whether it finally becomes P-complete. gives the partial negative answer: Constructing a maximum s-t flow in a directed graph whose edge weights are given in unary is in RNC; namely, k-connectivity for an undirected graphs is in RNC. Probably,α-connectivity provides the first example of gradually increasing complexities from NC to P-complete.
1993-09-27

On Parallelizability of α-Connectivity

スポンサーリンク

概要

著者

関連論文

スポンサーリンク