# Finding all circuits that contain a given edge

Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that traverses $e$ is in also in $H$.

As an example, suppose graph $G$ has vertices $V = \{1,2,3,4\}$ and edges $\{(1,2), (2,1), (2,3), (3,2), (3,1), (2,4), (4,3)\}$, and $e = (4, 3)$. The subgraph $H$ that the algorithm should output consists of the two circuits $2,4,3,2$ and $2,4,3,1,2$.

Of course, this problem can be solved by enumerating all circuits of $G$, but I'm hoping that someone here can come up with something better (that is, with strongly polynomial complexity, in the size of the graph) than that.

EDIT: I just found this post that solves the problem for undirected graphs, but it doesn't provide any directions for directed graphs. I don't see a straightforward generalisation to directed graphs from that post.

• So what you are after is, after removing $e = uv$, every vertex that lie on a path from $u$ to $v$, am I right? You can definitely do that in polytime using the polynomial time two-disjoint-paths algorithm, but there is probably a better way ... – Pål GD Mar 8 '15 at 6:44
• In the subgraph computed with $e = uv$, every vertex lies on a path from $v$ to $u$. Thanks, I'll check out the two-disjoint-paths algorithm. I must confess I have never heard of it. – robertdg Mar 8 '15 at 9:07
• I just found this post that solves the problem for undirected graphs, but it doesn't provide any directions for directed graphs. I don't see a straightforward generalisation to directed graphs from that post. – robertdg Mar 8 '15 at 15:02
• Isn't $H$ the strongly connected component that includes $e$ (if any)? – reinierpost Mar 9 '15 at 10:15
• No, consider a strongly connected graph $G$ with some edge $e$. Add a cycle in the following way: choose a random vertex $v$. Now add vertices $w_i$ to the graph and the cycle $C = v w_1 \ldots w_n v$. The resulting graph is still strongly connected, but cycle $C$ should not be in $H$. – robertdg Mar 9 '15 at 10:57

It should be NP-complete to compute, given an arc $e = uv$ of a directed graph $D = (V,A)$ whether there is a cycle containing some vertex $w$ using the arc $e$. The instance to this problem is $(D,e,w)$.
By reducing from back-and-forth (two-disjoint paths from $a$ to $b$ and from $b$ to $a$), given an instance $(D',a,b)$ of back-and-forth, construct the instance $D$ where you make two copies of $a$, $a_1$ and $a_2$ and an arc going from $a_1$ to $a_2$. The constructed instance is $(D,(a_1a_2),b)$.
Now, suppose there are two-disjoint paths from $a$ to $b$ and back, then there is a cycle from $a_2$ to $b$ and from $b$ to $a_1$, hence $b$ is on a cycle containing the arc $a_1a_2$. For the reverse direction suppose that $b$ is on a cycle traversing the arc $a_1a_2$. Then, in the original graph, there is a path from $a$ to $b$ and one from $b$ to $a$. qed