4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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 ... $\endgroup$ – Pål GD Mar 8 '15 at 6:44
  • $\begingroup$ 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. $\endgroup$ – robertdg Mar 8 '15 at 9:07
  • $\begingroup$ 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. $\endgroup$ – robertdg Mar 8 '15 at 15:02
  • $\begingroup$ Isn't $H$ the strongly connected component that includes $e$ (if any)? $\endgroup$ – reinierpost Mar 9 '15 at 10:15
  • $\begingroup$ 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$. $\endgroup$ – robertdg Mar 9 '15 at 10:57
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I was kind of afraid it would be NP-hard to construct the subgraph. It's interesting to see how such a seemingly simple problem is so difficult to solve in the presence of cycles. $\endgroup$ – robertdg Mar 10 '15 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.