In order to answer the questions of the types above, researchers started to devise graph preprocessing methods and graph simplifications, which transform an input graph into a smaller graph or a concise data structure, such that computations on the input graph can be transformed into more efficient computations on the simplified structure. Different computational goals call for different graph preprocessing methods; for example, the efficiency of exact distance queries can be increased by adding so-called 2-hop labels to the vertices [1]}, while the computation of a minimum cut can be improved by removing certain edges and resulting in a cut sparsifier [2]}.
