Given a directed graph G=(V,E) and an edge e?E, I\'m trying to come up with an a

Question

Given a directed graph G=(V,E) and an edge e?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.

Explanation / Answer

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, a1 and a2 and an arc going from a1 to a2. The constructed instance is (D,(a1a2),b).

Now, suppose there are two-disjoint paths from a to b and back, then there is a cycle from a2 to b and from b to a1, hence b is on a cycle containing the arc a1a2. For the reverse direction suppose that b is on a cycle traversing the arc a1a2. Then, in the original graph, there is a path from a to b and one from b to a. qed

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.