Constructing cliques using restricted backtracking
Mark Goldberg, Reid Rivenbergh · DIMACS series in discrete mathematics and theoretical computer science · 1996
. The restricted backtracking algorithmic paradigm is applied to the Maximum Clique Problem. The notion of backtracking coordinates is introduced. The program searches for those cliques whose backtracking coordinates are bounded by the values given in the input. 1. Introduction and motivation The problem of constructing a clique of the maximum size in a given graph, the clique problem, was proved to be NP-hard in [10] (see also [8] and [13] for a survey on the problem). Recently, it was proved ([1]) that even constructing a clique whose size is within a factor of n ffl of the maximum is NP-hard (here n is the vertex number and ffl ? 0). Nevertheless, we argue that these results do not necessarily imply the intractability of the problem "in practice." The essential difference between the theoretical model and the way the problem occurs in applications is as follows: ffl the size of the graph which can be stored in the memory of any computer is bounded; it cannot exceed 10 40 ---th...