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.


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