Randomized algorithm -- Elme 06:22, 3 February 2011 (UTC)
The algebraic characterization of dual factor-criticality easily yields a randomized polynomial algorithm to Problem 2.
A short explanation including working source code (in sage) is to be found here: here.
