View Forum Topic

Forums
CS332F
HardLife

Author	Message
rabbott Posts: 1649	Posted 22:04 Feb 19, 2014 \| Here is an example that shows that the strategy of recursively dropping nodes with a single link doesn't always get the right answer. Define graphA as 4 nodes all pairwise connected: List((1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4)) It has a hardness factor of 1.5: (6 edges)/(4 nodes) Define graphB as four nodes in a cycle. Let it includes one of the nodes from graphA: List((4,5), (5,6), (6,7), (7,4)) It has a hardness factor (on its own) of 1: (4 edges)/(4 nodes) Take the combination of graphC = graphA ++ graphB. It has a hardness factor of 1.43: (10 edges)/(7 nodes). That makes sense since one of its two subgraphs is harder and the other is less hard. But if you start with graphC, there are no singleton nodes to eliminate. So the algorithm would say that graphC can't be reduced to a harder graph. But in fact, graphA, a subset of graphC, is harder than graphC. I'll put HardLife back on the list of possible problems to think about. Last edited by rabbott at 22:15 Feb 19, 2014.
rabbott Posts: 1649	Posted 23:11 Feb 19, 2014 \| More generally, given any graph with hardness > 1, if you add a disconnected graph that consists of a simple cycle (hardness = 1) to it the combination will be worse that the original. This can be solved by looking at all disconnected pieces separately. But as in the previous example, if the added cycle is attached to the original graph, it may cause a problem.

Author

Message

rabbott

Posts: 1649

Posted 22:04 Feb 19, 2014 |

Here is an example that shows that the strategy of recursively dropping nodes with a single link doesn't always get the right answer.

Define graphA as 4 nodes all pairwise connected: List((1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4))

It has a hardness factor of 1.5: (6 edges)/(4 nodes)

Define graphB as four nodes in a cycle. Let it includes one of the nodes from graphA: List((4,5), (5,6), (6,7), (7,4))

It has a hardness factor (on its own) of 1: (4 edges)/(4 nodes)

Take the combination of graphC = graphA ++ graphB. It has a hardness factor of 1.43: (10 edges)/(7 nodes). That makes sense since one of its two subgraphs is harder and the other is less hard.

But if you start with graphC, there are no singleton nodes to eliminate. So the algorithm would say that graphC can't be reduced to a harder graph. But in fact, graphA, a subset of graphC, is harder than graphC.

I'll put HardLife back on the list of possible problems to think about.

Last edited by rabbott at 22:15 Feb 19, 2014.

rabbott

Posts: 1649

Posted 23:11 Feb 19, 2014 |

More generally, given any graph with hardness > 1, if you add a disconnected graph that consists of a simple cycle (hardness = 1) to it the combination will be worse that the original. This can be solved by looking at all disconnected pieces separately. But as in the previous example, if the added cycle is attached to the original graph, it may cause a problem.