  In this work we study preprocessing for tractable problems when part of the
input is unknown or uncertain. This comes up naturally if, e.g., the load of
some machines or the congestion of some roads is not known far enough in
advance, or if we have to regularly solve a problem over instances that are
largely similar, e.g., daily airport scheduling with few charter flights.
Unlike robust optimization, which also studies settings like this, our goal
lies not in computing solutions that are (approximately) good for every
instantiation. Rather, we seek to preprocess the known parts of the input, to
speed up finding an optimal solution once the missing data is known.
  We present efficient algorithms that given an instance with partially
uncertain input generate an instance of size polynomial in the amount of
uncertain data that is equivalent for every instantiation of the unknown part.
Concretely, we obtain such algorithms for Minimum Spanning Tree, Minimum Weight
Matroid Basis, and Maximum Cardinality Bipartite Maxing, where respectively the
weight of edges, weight of elements, and the availability of vertices is
unknown for part of the input. Furthermore, we show that there are tractable
problems, such as Small Connected Vertex Cover, for which one cannot hope to
obtain similar results.
