Minimum set of nodes through which the eah path goes

[kwedeer]

I am seeking for the following algorithm:
The undirected graph G is given by list of edges, e.g. like 1-2, 2-3, 1-4,... and G has the S and T (source and target vortices, but as G is undirected graph, the they have only the follwing meaning - we sholud simply consider each path that can be from S to T). One should find the minimum set of nodes of G, which can be denoted by MS, with the property that each path from S to T has at least one vertex from MS. One should find the size (cardinality) of MS and also list the vertices in it. I guess, the polynomial time algorithm should exist.

Can anyone suggest to which broader category of algorithms this problem can belong to (e.g. like max flow or bipartite max spanning cover algorithm, or like that)?

[mf]

First, find all bridges in the graph. This can be done in O(V+E) time with a modification of DFS.

Bridges separate biconnected components of the graph, i.e. if you remove all bridge edges, then in each of remaining connected components there will be two or more disjoint paths between any pair of vertices. So you can't be sure at all which vertices are visited in a biconnected component, except for path's endpoints.

Find which bridges will be visited by a path from source to destination (all paths have the same set of bridges, because if you contract biconnected components you'll get a tree; so just find bridges in any such path), and the answer is set of endpoints of these bridges, union source and destination vertex.
This is the set of vertices through which any path from source to destination will pass, which is what you need, as I understand.

[kwedeer]

OK - I started to implement the solution and my plan was - to find the strongly connected components SSC for the first instances. There is nice algorithm in Kormen for this:
1) one should make DFS for initial graph G and determin how the vortices are ordered according to time - say in some array f;
2) one should find tranposed graph (simply - by inverting direction of edges) GT
3) one should make DFS in GT, where the main loop over the vortices is done not in the arbitrary order as in point 1, but in order thatr was find in point 1 - f. And in this time one should be able to read SSC.

But now I have started to comprehed about efficient way how to read bridges from the data about components. The first idea that comes into mind, is simply go through all the edges of G (namely, with source and target removed) and check - if edge belong to different SSCs then it is bridge, if both endpoints belong to the same SSC, then it is not bridge. So - if we maintain the array (with the length - number of vertices), whose each element keeps the number of SSC to which the vertex belong, then, I guess, this works still in linear time. Well - now I start to think, that maybe there is some really nice algorithm exactly for bridges, that doesn't require the computations of SSCs?

Another point of confusion. I have read the suggestion, that there can be different sets of vertices (for the solution in the initial task), but that is in contradiction to the general idea, that the set, which should be solution, is exactly the set of endpoints of bridges and this set shold be unique by definition (there can't be alternatives for bridges). Well - I guess that this notes about non-uniqueness is simply for confusion.

[mf]

Strongly-connected components are defined for directed graphs. And we have an undirected graph here. I have no idea how you could use an SCC algorithm to find bridges in it.

A DFS modification which I've mentioned goes like this:

Code: Select all

int low[MAXN], seen[MAXN], counter;

void dfs(int x, int parent)
{
    low[x] = seen[x] = ++counter;

    for each edge x->y {
        if (y != parent) {
            if (seen[y] == 0) {
                dfs(y, x);
                low[x] = min(low[x], low[y]);
                if (low[y] == seen[y])
                    printf("Edge (%d, %d) is a bridge.\n", x, y);
            } else {
                low[x] = min(low[x], seen[y]);
            }
        }
    }
}

...
memset(seen, 0, sizeof(seen));
counter = 0;
dfs(starting_vertex, -1);

This algorithm is also mentioned in Cormen's book, in a problem about biconnected components.

[kwedeer]

You are right about condition, that graph should be undirected. Well - I agree about bridges, but I would like to add, that finding the bridges is not enoug, the complete set should be union((send of endpoitns of bridges) and (articulation points)). E.g. the following graph shows why articulations points are important (source and target with the relevant edges are removed, they should be on the left and right sides (not top/bottom)):

Code: Select all

V                 V
- --          --  -
-    -- V --     -
- --          --  -
V                 V

Yes - there are some word in Cormed about biconnected components and articulation points, but sadly:
1) they are on part of excersise and so - expliciat algorithms are not given
2) there is term 'simple cycle' in the definition of 'biconnected component' and no explataion what is meant by 'simple', one can have multiple variant how imagination can work

Besides - I feel that I will have to start from the very zero - because - when I am looking on the figure 23.10 of Cormen and I suggest adding source and target in the left and right, then I can clearly see - that the minimum set throught one should go through can be even of size of one vertex. So - one should now find all the bridges, but one should find only one bridge if such exist at all and if seapartes the source and target. But there is wast class of bridgeless graphs...

Well, one can look on other simple example, e.g. ractangle as inner graph (i.e. source and target removed). What are the components or articulations points of this rectangle? I guess, the direction to which one should comprehend, is something about finding some cut...

[kwedeer]

OK - I am back to this very problem and I now I am considering the hypothesis, that this minimal set should be a graph cut - i.e. set of nodes, such, that if they are removed (each node of this set is split into two nodes and each part is given to subgraph with source and subgraph with target), then the graphs splits into two non-connected graphs. Then - the question is - is there any algorithm of finding such cut.

[kwedeer]

Hi, guys!. I guess I have found the right notions - the set under investigation is minimum vertex cut, see teh definition: http://www.nist.gov/dads/HTML/minvertexcut.html.

Now I start to believe that success is really some 10% of talent and 90% of work and the latest portion includes some knowledge as well.

[ChPravin]

I just wanted to seek an explanation to the following code to find the number of bridges in an undirected,connected graph:
What is the use of the low array here?

int low[MAXN], seen[MAXN], counter;

void dfs(int x, int parent)
{
low[x] = seen[x] = ++counter;

for each edge x->y
{
if (y != parent)
{
if (seen[y] == 0)
{
dfs(y, x);
low[x] = min(low[x], low[y]);
if (low[y] == seen[y])
printf("Edge (%d, %d) is a bridge.\n", x, y);
}
else
{
low[x] = min(low[x], seen[y]);
}
}
}
}

...
memset(seen, 0, sizeof(seen));
counter = 0;
dfs(starting_vertex, -1);

[mf]

low[x] = minimum of seen[x] and seen[y] among all y, such that there exists a back edge (z, y) for some z in x's subtree of the DFS tree. Basically, if low[x] < seen[x], then starting in x, going to an x's descendant in DFS tree and using some back edge we can climb above x in DFS's tree.

If this sounds like abracadabra to you, read CLRS's chapter 22 for theory behind depth-first search.

[ChPravin]

thx for the reply
yes i have to read that chapter