We describe and analyze test case generators for the maximum clique problem (or equivalently for the maximum independent set or vertex cover problems). The generators produce graphs with specified number of vertices and edges, and known maximum clique size. The experimental hardness of the test cases is evaluated in relation to several heuristics for the maximum clique problem, based on neural networks, and derived from the work of A. Jagota. Our results show that the hardness of the graphs produced by this method depends in a crucial way on the construction parameters; for a given edge density, challenging graphs can only be constructed using this method for a certain range of maximum clique values; the location of this range depends on the expected maximum clique size for random graphs of that density; the size of the range depends on the density of the graph. We also show that one of the algorithms, based on reinforcement learning techniques, has more success than the others at solving the test cases produced by the generators. In addition, NP-completeness reductions are presented showing that (in spite of what might be suggested by the results just mentioned) the maximum clique problem remains NP-hard even if the domain is restricted to graphs having a constant edge density and a constant ratio of the maximum clique size to the number of vertices, for almost all valid combinations of such values. Moreover, the set of all graphs produced by the generators, and having a constant ratio and edge density, is also NP-hard for almost all valid parameter combinations.

An adaptation to multiple blocks of a two-block network partitioning algorithm by Krishnamurthy was previously presented and analyzed by the author (see ibid., vol.38, p.62-81, 1989). The algorithm assumed one of several possible generalizations of two-way partitioning to multiple-way partitioning. The problem of adapting this algorithm to work with different generalizations more suitable for other types of applications of network partitioning is considered. It is shown that certain portions of the algorithm must be revised in order to maintain a relatively low time complexity for the modified algorithms. Experimental results are given.>

Polynomial-time Turing machines that output instances of a given language are considered, where the instances are required to have a certain length specified by the input. Two types of generating machines are investigated. The first, called a constructor, is deterministic and outputs one string in the language having the specified input length, if such a string exists. A generator is nondeterministic and may output different strings in the language using different computations on the same input; it is required, however, that for any string in the language satisfying the input constraint, there be some computation of the generator on this input that produces the string. Although most P and NP languages examined appear to have such polynomial-time constructors and generators, it is shown that the question of whether all NP languages have such machines is related to other open questions in complexity theory and that even under the assumption that P is not equal to NP, the question cannot be resolved using techniques that relativize. More general and/or flexible types of generators are also considered; namely, generators based on other parameters besides length; generators that are not necessarily capable of outputting all of the instances in the language satisfying the input constraint; and generators where the output instance does not need to satisfy the input constraint exactly. Several results are proved about the existence of such generators for various types of languages.

A multiple-block network partitioning algorithm adapted from a two-block iterative improvement partitioning algorithm is presented. This adaptation of the algorithm and of the level gain concept to multiple blocks seeks to improve the partition uniformly with respect to all blocks as oppose to making repeated uses of two-way partitioning. Appropriate data structures and a complexity analysis are presented, as well as experimental results. The experiments indicate that the optimal number of levels to use depends on the number of blocks and the net size and degree distributions of the network, but it varies little with the size of the network. In particular, higher levels are increasingly useful as the number of blocks in the partition increases. Theoretical results agree with the experimental results and form the basis for a predictor which, given a network and the desired number of blocks, approximates the optimal number of levels.>