Let G(V,E) be an weighted, undirected, K-connected graph. Let N be subset of V. What is the best way to find the smallest connected subgraph G'(V',E') of G(V,E) such that N is a subset of V' and induced subgraph G(V',E') is (K-1)-vertex connected?
The vertex-connectivity of an input graph G can be computed in polynomial time in the following way consider all possible pairs (s, t) of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for (s, t) is the number of pairwise vertex-independent paths between them, encode the input by doubling each vertex as an edge to reduce to a computation of the number of pairwise edge-independent paths, and compute the maximum number of such paths by computing the maximum flow in the graph between s and t with capacity 1 to each edge, noting that a flow of k in this graph corresponds, by the integral flow theorem, to k pairwise edge-independent paths from s to t.
Already this procedure is practically slow. Not to speak of an related optimization problem which might make the whole task hard. Anyway, i think that in your problem you don't need the weightedness of the edges, am i right?...
http://en.wikipedia.org/wiki/K-vertex-connected_graph
Dear Thomas,
Thank you for reply. But my problem requires more alongwith checking the subgraph to be (K-1)-vertex connected. If the subgraph G(V',E') of graph G(V,E) is not (K-1)-vertex conncected then how to extend (by adding the edges and vertices from graph G(V,E)) G(V',E') to make (K-1)-vertex conncected ?
For example: K=2 this problem is similar to steiner tree problem. But I am not able to understant how to approach when K>2.
In addition to the material pointed out by Prof. Thomas Korimort, Please have a look at the following links:
http://win.uantwerpen.be/~vanhoudt/graph/connectivity.pdf
http://rutcor.rutgers.edu/~kborys/k%20connected.pdf
https://people.mpi-inf.mpg.de/~elbassio/pub/paper.pdf
http://lca.ceid.upatras.gr/~kirousis/publications/j23.pdf
Hope that these references will be useful to you..
If you want to chose (or are given) N subset of V (as it seems to be), then it can also be that there is no V' superset of N and subset of V whose induced subgraph of G is k-1 connected. As i don't know your exact problem from where you started i will join Sudev Naduvath and append some links that will give you an overview about variations of the problem. As my idea first was that you could simply generate all possible choices of subsets V' of V and superset of N and test each for the degree of connectivity, this approach is obvious but maybe practically not feasible (how many different vertex sets would have to be tested. The last reference is already given by Sudev Navudath.
http://csis.bits-pilani.ac.in/faculty/sundarb/courses/old/spr14/daa/eval/assign/papers/approx/subgraphs.pdf
https://people.mpi-inf.mpg.de/~elbassio/pub/paper.pdf
http://lca.ceid.upatras.gr/~kirousis/publications/j23.pdf
Thank you very much Thomas sir and Sudev sir for your interest.
Please find the attachement (named as problem.pdf) , here I am attaching the algorithm of my problem that will give more insight about the problem .
Please give your valuable comments.
Thomas Sir,
Could you please suggest me any standard approach to approach above problem written in attached pdf.
Looking forward to your response.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs