Irregular problems

I am not aware of any satisfactory definition for irregular problem in the context of parallel computation, though there is a recognizable class of such problems that crop up in diverse application domains including graph analytics, discrete optimization, games, simulation, and visualization. A classic example of an irregular problem is to determine whether or not an undirected graph is connected. We include as computational resources: processing, memory space, and bandwidth. Then, my working definition is this: a computation is irregular to the extent that determining with any accuracy the computational resource requirements as a function of time to solve it as a function of its input requires computational resources comparable to the computational resources required to solve it. A problem is irregular when its most favorable parallel solution is irregular. Put another way, we recognize that a problem is irregular when allocating resources to its solution is far better done dynamically than statically. To determine whether or not a graph is connected can be done trivially sequentially by any graph traversal algorithm such as DFS or BFS; to do so with maximal parallelism, a link-and-compress approach can be used, but is not usually the most work-efficient. There are any number of algorithmic variations along the spectrum. But, there doesn't seem to be any ways to "sample the graph input" so as to determine which algorithm is most efficient; predicting the resources required appears to be as hard as just running the computation.