0
$\begingroup$

Let $G$ be a simple, bridgeless (2-edge connected), undirected graph and let $P$ be an arbitrary path between vertices $u$ and $v$ of $G$. Will $u$ and $v$ be in the same component of $G \setminus P$?

Update: I had to recognize that removing $P$ can destroy the connection between $u$ and $v$. Let us consider the following 2-edge connected graph:

enter image description here

Indeed, there are two independent paths $u$ and $v$, whose edges are denoted with "1" and "2". Nevertheless, if $P$ is choosen such that their edges would be the red ones, then there is not another $Q$ path independent of $P$. Do you have any idea what to do in these cases?

$\endgroup$
0
$\begingroup$

Apologies for the original error in not spotting the counterexample! The problem seems to be that, in removing a path, you create a graph with a bridge in the process. What I said about 2-connected bridgeless graphs being a union of subcomponents that are cycle graphs seems to make sense - a cycle graph is the minimal example of this type of graph and if you add edges then it does not change this property. You can add more cycles through shared vertices and edges of existing property and this property still does not change. Where the problem occurs in the counterexample is that we have one shared edge and two shared vertices between two 4-cycles, but you can easily see how that can be extended more generally to cause a problem.

The minimum number of edges in a simple connected graph on n nodes is n-1 (a tree). Note that removing the path in the counterexample brings the number of edges below this number and so we must be creating disjoint graphs somewhere in the process! This holds true for any graph, so if we are removing a path between u and v and the total number of edges falls below n-1, then we should check to see that u and v are not in disjoint graph components. The opposite does not generally hold true - if a graph has more than n-1 edges is not necessarily connected. That is easy to see if you connect a sufficiently large complete graph onto the far end of one of the sides of your example - the path still disconnects u and v even though it can have a lot more than n-1 edges. I just mean to say that this cannot be the basis of a test to see if u and v are still connected.

If you want to find two paths between u and v such that removing either one does not leave u and v disconnected, you should probably look into a cycle detection algorithm for undirected graphs for finding a cycle - preferably minimal - that contains both u and v. Removing both paths and keeping u and v connected is impossible without stronger restrictions on the type of graph if you consider the cycle example.

$\endgroup$
7
  • $\begingroup$ Thank you very much! My goal is to determine a $Q$ path which is edge disjoint from $P$. Is it a good way to remove $P$ from $G$ and search for a path between $v$ and $u$ in $G \setminus P$? $\endgroup$
    – Roli
    Apr 4 '19 at 13:13
  • $\begingroup$ Any two vertices in this type of graph are part of a subgraph H of G that is a cycle graph on at least 3 vertices. If you can find this subgraph then Q will be H\P. Are you looking for an algorithm to do this on a particular given graph? $\endgroup$ Apr 4 '19 at 13:42
  • $\begingroup$ I would like to implement an algorithm which provides $P$ and $Q$ such that $P$ and $Q$ are the shortest paths (only positive weights are allowed) between $u$ and $v$ in $G$ and $G \setminus P$, respectively. I should do this for all $v$ at a fixed $u$. Do you have any idea what is the cheepest way to perform this procedure? $\endgroup$
    – Roli
    Apr 4 '19 at 14:49
  • $\begingroup$ If you have a weighted graph and you want the shortest path, then Dijkstra's algorithm is the classic way to show this. It will find the shortest path between v and u so you can assign that to P and then once you remove that you can apply the same algorithm to find Q. Also check out the other algorithms:en.wikipedia.org/wiki/Shortest_path_problem#Undirected_graphs and en.wikipedia.org/wiki/Dijkstra%27s_algorithm If you aren't using weighted graphs, then assign all the weights in the graph the value 1. $\endgroup$ Apr 4 '19 at 15:28
  • 1
    $\begingroup$ There is a serious issue about the $P/Q$ approach. See my answer to my own question. $\endgroup$
    – Roli
    Apr 5 '19 at 10:54

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.