Оптимальное расконтуривание

Интересно каким образом можно эффективно решать следующие задачи:
1. Дан ориентированный граф. Какое минимальное количество ребер надо удалить, чтобы получить бесконтурный граф.
2. Дан ориентированный граф. Какое минимальное количество ребер надо переориентировать чтобы получить бесконтурный граф.