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
extended version of the paper contains the proofs of the statements.