Cheap and Secure Web Hosting Provider : See Now

[Solved]: Finding all circuits that contain a given edge

, , No Comments
Problem Detail: 

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.

Asked By : robertdg

Answered By : Pål GD

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback