α-Connectivity: A Gradually Nonparallel Graph Problem

DOI

Search this article

Description

In the class NP, gradually intractable problems whose complexity changes from P to NP-complete are not rare. Most problems prefixed by k-, such as k-clique and k-vertex cover, fall into this category. In the class P, however, gradually unparallelizable problems are rare. As the gradually intractable problems nicely exhibit fundamental differences between P and NP-complete, gradually unparallelizable problems are strongly expected to play the same role inside P. In this paper, we will introduce a new problem called α-connectivity and show that its 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 expressed by two positive constants c and e as α = cn e .

Journal

Details 詳細情報について

Report a problem

Back to top