This problem has been bugging me, but I cant find a simple solution to it. Say I have a general graph of E edges and V verticies, ok? Assume that all verticies are connected to all other verticies. Here's the problem: Form a spanning tree, such that there are at least 3 linearly independent simple paths from any node to any other node. Or, basicially: In some sub-graph (which is what we're looking for), you have to have a path from any node to any other node (spanning tree). However, there must be multiple independent routes that connecting any of the nodes (verticies) in the graph. So if any single node were to be removed, there would still be two independent routes from any node to any other node in the remaining tree. eg. this graph: A-B-C-D-E does not satisfy the considitions; although it is a spanning tree, there is only one simple path from a node to any other node. This graph however: A-D (D links to B) |\| B-E If fine, because there are at least three independent paths from any node to any other node; eg. A->E; AE, ADE, ABE, etc. For small numbers of verticies the tree is simply an everything-connects graph. =P Its larger trees where problems start appearing... The best idea I can come up with is to remove edges randomly, then check the graph to see if the properties required are still valid, and if not, back track and try again. Needless to say; this is not a good solution, and how optimal the solution is when you have weighted edges is totally random. =p Any suggestions? All ideas welcome. Edit - Spelling error. [edited by - Shadow Mint on June 18, 2002 10:00:35 PM]

I think it might only be possible for perfect n-gon shapes -
tetrahedrons, cubes, octeherons, dodecahedrons (20), etc... like AD&D dice (but not d10''s).

quote:

---

Original post by Shadow Mint
Here''s the problem: Form a spanning tree, such that there are at least 3 linearly independent simple paths from any node to any other node.

---

To my knowledge, most algorithms for finding subgraphs in arbitrary graphs is NP-hard. If you''re desperate for an answer I''ll pass the problem along to a colleague who''s an expert in the area.

Let me know...

Cheers,

Timkin

Well, this isnt urgent, but like I said, I cant find a decent solution. If you'd care to ask someone, I'd welcome it; I'm certainly at a dead end.

My solution is to:

1) Sort the edges by weight
2) While (edges left)
3) -- Remove the largest weight edge from the graph
4) -- If the graph is no longer valid (* see below)
5) ---- Put the edge back into the graph, but not the sorted list.

(Nb. Sorting done because in this case I'm trying to get a minimum cost tree; but it doesn't matter really; Any tree that obeys the rules is fine).

but...I can usually come up with a better solution by hand if I try (hard for large # of verticies though), and it takes a very long time.

* Validity is determined by exploration of the graph. At the moment this is just a basic explore-every-case recursive search which terminated when three independent routes are identified, from every node to every other node (see how this could a very long time for many verticies?). Maybe a dynamic programming solution would be handy...

*shrugs* I dont think I'm approaching it the right way. Even some suggestions on ideas to think about are welcome.

PS. Magmai: As far as I can tell, there is one solution that will for for any number of nodes > 4. A ring of nodes all connected to form the ring, with the final node in the center, connected to every other node. In this case, there are ALWAYS at least three routes to any other node; left around the ring, right around the ring, or through the center.

However, I that is not optimal for a weighted graph, and tends toward clustering around the center (which is bad if you had to rebalance the graph after removing nodes; since one of them would be the central node, connected to N-1 other nodes; ie. lots of work).

Anyway; point is, a variety of topologies have the required property (consider say three central nodes, each connected to 1/3 of ring, and to all other central nodes, etc. These are just trivial ones that my mind can think of though. =p I'm pretty sure an optimal graph would look prety weirdly interleaved).

[edited by - Shadow Mint on June 19, 2002 5:30:43 AM]

Okay, so before I go and ask someone else a question, let''s make sure I understand what it is you are trying to do.

From your first post:

I assume you are starting with a fully-connected graph: G = < V,E >
You wish to find a subgraph that has the property: for any two nodes in the subgraph there exists at least 3 paths between those nodes.

Question: Can these three paths share at least one edge or must they be completely independent of each other?

Timkin

*nods* No.

The paths must be totally independent; they cannot share any single vertex, except the beginning and end verticies.

Careful though; vertex, implies not edge, but also no other edge connecting to the given vertex.

Optimality is for a minimum number of edges in the resulting graph, and a minimum number of edges for a minimum cost in a weighted graph.

Ouch, they''re some fairly heavy constraints. Okay, I''ll see what I can come up with among my colleagues.

Cheers,

Timkin