It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity. We introduce a new way for encoding graph problems, based on CNF or ...