×

Succinct representations of graphs. (English) Zbl 0538.68053

Summary: For a fixed graph property Q, the complexity of the problem: Given a graph G, does G have property Q? is usually investigated as a function of \(| V|\), the number of vertices in G, with the assumption that the input size is polynomial in \(| V|\). In this paper the complexity of these problems is investigated when the input graph is given by a succinct representation. By a succinct representation it is meant that the input size is polylog in \(| V|\). It is shown that graph problems which are approached this way become intractable. Actually, no ”nontrivial” problem could be found which can be solved in polynomial time. The main result is characterizing a large class of graph properties for which the respective ”succinct problem” is NP-hard. Trying to locate these problems within the P-Time hierarchy shows that the succinct versions of polynomially equivalent problems may not be polynomially equivalent.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI