The variable-sharing graph of a polynomial system of equations has one vertex for each variable, and an edge between two variables if and only if those variables appear together in at least one equation. If this graph is disconnected, then the system is actually two separate systems that can be solved individually. This can provide a huge speed-up, but is unlikely to occur either randomly or in applications. However, it may be the case that deleting a small number of vertices c disconnects the variable-sharing graph in a balanced fashion, so that the ratio of the sizes of the larger and smaller components is roughly less than two.

If this is the case, then we demonstrate two techniques, one for small fields and one for large fields, to split the system. For small finite fields GF(q), we simply iterate through all possible q^c guesses of the c variables, and solve the separated systems. If the field is infinite or finite but large (i.e. has more than roughly five members), we separate the system with resultants. We present two methods for detecting this condition and identifying the c variables.

First, when c is small, or when { V } is small, one can run a large series of depth-first searches. Alternatively, when c or {V } is large, we show how to use off-the-shelf balanced edge cut determining software to generate a "reasonable" vertex cut. Also, we state a condition for a system of equations to be immune to this approach.

We present experiments which show that this condition can occur in practice, with very sparse polynomial systems. We also present four applications. The first is to implant/detect a trapdoor in the stream cipher QUAD; the second is to show a security property of the authentication system HB/HB+; the third has to do with "the Apollonius Problem" from Euclidean Geometry; the fourth is the "cube game" from multiparty game theory.