Hi
I'd like some help with identifying this problem or just getting some
ideas on how to solve it. I have a standard undirected simple graph G
= {N, E} and vertex sets V_1, V_2,, V_n where each vertex set is a
connected component of G, each vertex of G can belong to at most one of
these sets and each set is a proper subset of N. Edges of G have an
associated cost. My problem is to choose the edge set of minimum cost
whose removal will result in there being no paths between any two
vertex sets V_i, V_j.
thanks
Stephen

I'd like some help with identifying this problem or just getting some
ideas on how to solve it. I have a standard undirected simple graph G
= {N, E} and vertex sets V_1, V_2,, V_n where each vertex set is a
connected component of G, each vertex of G can belong to at most one of
these sets and each set is a proper subset of N.

So you need to find V_1, V_2 V_n?
(which would only mean that the vertices are naturally clustered)

Edges of G have an
associated cost. My problem is to choose the edge set of minimum cost
whose removal will result in there being no paths between any two
vertex sets V_i, V_j.

Have you tried using K-means or some other clustering algorithm?

KS

Stephen wrote:
Hi

I'd like some help with identifying this problem or just getting some
ideas on how to solve it. I have a standard undirected simple graph G
= {N, E} and vertex sets V_1, V_2,, V_n where each vertex set is a
connected component of G, each vertex of G can belong to at most one of
these sets and each set is a proper subset of N. Edges of G have an
associated cost. My problem is to choose the edge set of minimum cost
whose removal will result in there being no paths between any two
vertex sets V_i, V_j.

I'm missing something here. If you delete every edge (x,y) where x\in
V_i and y\in V_j for some i \neq j, then you've eliminated all paths
between components. If you leave any such edge in, you have a path
between two components. So where's the decision? ( did you mean you
want to disconnect a specific pair of components from each other, rather
than disconnecting *every* pair V_i, V_j?)

/Paul

Paul A. Rubin wrote:
Stephen wrote:

I'd like some help with identifying this problem or just getting some
ideas on how to solve it. I have a standard undirected simple graph G
= {N, E} and vertex sets V_1, V_2,, V_n where each vertex set is a
connected component of G, each vertex of G can belong to at most one of
these sets and each set is a proper subset of N. Edges of G have an
associated cost. My problem is to choose the edge set of minimum cost
whose removal will result in there being no paths between any two
vertex sets V_i, V_j.
--
I'm missing something here. If you delete every edge (x,y) where x\in
V_i and y\in V_j for some i \neq j, then you've eliminated all paths
between components. If you leave any such edge in, you have a path
between two components. So where's the decision? ( did you mean you
want to disconnect a specific pair of components from each other, rather
than disconnecting *every* pair V_i, V_j?)

You're not reading carefully.
Methinks that this is a homework problem
designed to test one's vocabulary.
Given the premises, the solution is trivial, even with negative edges.

This isn't a homework problem and isn't trivial. I think the
misunderstanding here is that each vertex can belong to at most one of
the sets V_i but doesn't have to, so there are a number of ways of
disconnecting V_i, V_j.

I've done some more research and come across the multiway cut problem
which is NP-hard for k>2, described as follows: Given an undirected
graph with edge costs and a subset of k nodes called terminals, a
multiway cut is a subset of edges whose removal disconnects each
terminal from the rest.

So if I shrink each of my sets V_i to a single vertex and readjust the
edge costs etc I should be able to use a known method to solve my
problem. I've got some side constraints to include but this seems like
a good place to start.

cheers

Stephen

This isn't a homework problem and isn't trivial. I think the
misunderstanding here is that each vertex can belong to at most one of
the sets V_i but doesn't have to, so there are a number of ways of
disconnecting V_i, V_j.

How would you disconnect V_i and V_j if the a node is present in both
sets? Can you remove nodes from sets? Can you switch nodes between
sets?

I've done some more research and come across the multiway cut problem
which is NP-hard for k>2, described as follows: Given an undirected
graph with edge costs and a subset of k nodes called terminals, a
multiway cut is a subset of edges whose removal disconnects each
terminal from the rest.

This means that V_i, V_j V_n are not given, and you need to find
them (contradictory to your original problem). I think the two are
completely different problems.

Stephen wrote:
This isn't a homework problem and isn't trivial. I think the
misunderstanding here is that each vertex can belong to at most one of
the sets V_i but doesn't have to, so there are a number of ways of
disconnecting V_i, V_j.

Assuming your ire isn't totally senseless,
you've misstated your problem.
Try again.
This time you might want to state its origin.
You should also explicitly state
its inputs, its outputs, its feasible set,
and its objective function.