For an unfortunate circumstance, 
 in the published version  an (incorrect) "if and only if" has 
slipped into the statement of Proposition 2 instead of the
correct "only if". 
This is just a typing error, which does not affect the correctness of
 the algorithms since they were based on the  correct "only if" version.
The link above refers to a corrected version, in which
a couple of sentences in blue have beed added in order to highlight this
fact. 
The 
<A HREF="http://disi.unitn.it/~rseba/tacas10_extended.pdf">
extended version</A> of the paper contains  the proofs of the statements.