Efficient and automated screening of gaseous or liquid samples to detect novel compounds based on their mass spectral fingerprints (non-target screening) is an ongoing computational challenge that goes beyond standard library-based approaches. We present a novel algorithm that uses combinatorial and directed graph methods, taking into account chemical rules, to automatically assign high-resolution mass spectral peaks from gas-chromatography-separated time-of-flight mass-spectroscopy (GC-TOF MS) measurements to possible chemical formulas by considering possible fragmentation pathways. In a further step, this information is used to reconstruct the chemical formula of likely molecular parent ions. We show how this technique can be used to detect unknown contaminants in pre-concentrated air samples and how the algorithm can be extended to reconstruct not only the molecular formula but also the chemical structure of the parent ion.