You are given a directed graph $G=(V,E)$ with capacities $c(e) \in R^+$ and a set of edges $E_1 \subset E$. You want to find a cycle $C = (v_1, v_2), (v_2, v_3) ... (v_n, v_1)$ in the graph under the constraint that the capacity of the cycle is not bottlenecked exclusively by an edge $e \in E_1$ or $\exists e \in C, e \notin E_1 \: c(e) = \min\limits_{e_1 \in C} c(e_1)$
I know finding a cycle without constraints is easy using DFS search. My question is can the method be extended to solve the constrained problem while maintaining good performance.
Here is a polynomial algorithm (which can probably be improved):
For each $e=(u,v) \notin E_1$, take the graph $G\setminus \{e'\in E,c(e') < c(e)\}$ and find if there is a path from $v$ to $u$. If such a cycle exists, it will be found when testing the edge $e$ minimizing $c$ in the cycle.
Edit: Here is a more efficient algorithm. Compute the all-pairs shortest path on the graph, with maximization of the bottleneck as the distance. This can be done using Floyd-Warshall, by replacing addition with a min, and instead of choosing the minimum value between the two possibilities, you take the max. Then for each edge $e=(u,v)\notin E_1$, you check if there is a path from $v$ to $u$ with a bottleneck greater than $c(e)$. This is $|V|^3$, compared to the $|E|^2$ given above.