diff --git a/cycle_breaker.cc b/cycle_breaker.cc
index 0998dac..f9e3de6 100644
--- a/cycle_breaker.cc
+++ b/cycle_breaker.cc
@@ -77,6 +77,8 @@
   CHECK_GE(stack_.size(), 2);
   Edge min_edge = make_pair(stack_[0], stack_[1]);
   uint64_t min_edge_weight = kuint64max;
+  const int kMaxEdgesToConsider = 4;
+  int edges_considered = 0;
   for (vector<Vertex::Index>::const_iterator it = stack_.begin();
        it != (stack_.end() - 1); ++it) {
     Edge edge = make_pair(*it, *(it + 1));
@@ -89,6 +91,9 @@
       min_edge_weight = edge_weight;
       min_edge = edge;
     }
+    edges_considered++;
+    if (edges_considered == kMaxEdgesToConsider)
+      break;
   }
   cut_edges_.insert(min_edge);
   stack_.pop_back();
@@ -106,6 +111,17 @@
   }
 }
 
+bool CycleBreaker::StackContainsCutEdge() const {
+  for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
+        e = stack_.end(); it != e; ++it) {
+    Edge edge = make_pair(*(it - 1), *it);
+    if (utils::SetContainsKey(cut_edges_, edge)) {
+      return true;
+    }
+  }
+  return false;
+}
+
 bool CycleBreaker::Circuit(Vertex::Index vertex) {
   // "vertex" was "v" in the original paper.
   bool found = false;  // Was "f" in the original paper.
@@ -122,8 +138,11 @@
       HandleCircuit();
       found = true;
     } else if (!blocked_[*w]) {
-      if (Circuit(*w))
+      if (Circuit(*w)) {
         found = true;
+        if (StackContainsCutEdge())
+          break;
+      }
     }
   }
 
diff --git a/cycle_breaker.h b/cycle_breaker.h
index e9bb1e4..359f55b 100644
--- a/cycle_breaker.h
+++ b/cycle_breaker.h
@@ -35,6 +35,7 @@
   void HandleCircuit();
   void Unblock(Vertex::Index u);
   bool Circuit(Vertex::Index vertex);
+  bool StackContainsCutEdge() const;
 
   std::vector<bool> blocked_;  // "blocked" in the paper
   Vertex::Index current_vertex_;  // "s" in the paper
diff --git a/cycle_breaker_unittest.cc b/cycle_breaker_unittest.cc
index 1c81e54..59d6825 100644
--- a/cycle_breaker_unittest.cc
+++ b/cycle_breaker_unittest.cc
@@ -80,6 +80,77 @@
 }
 }  // namespace {}
 
+
+// This creates a bunch of cycles like this:
+//
+//               root <------.
+//    (t)->     / | \        |
+//             V  V  V       |
+//             N  N  N       |
+//              \ | /        |
+//               VVV         |
+//                N          |
+//              / | \        |
+//             V  V  V       |
+//             N  N  N       |
+//               ...         |
+//     (s)->    \ | /        |
+//               VVV         |
+//                N          |
+//                 \_________/
+//
+// such that the original cutting algo would cut edges (s). We changed
+// the algorithm to cut cycles (t) instead, since they are closer to the
+// root, and that can massively speed up cycle cutting.
+TEST(CycleBreakerTest, AggressiveCutTest) {
+  int counter = 0;
+  
+  const int kNodesPerGroup = 4;
+  const int kGroups = 33;
+  
+  Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
+  
+  const Vertex::Index n_root = counter++;
+
+  Vertex::Index last_hub = n_root;
+  for (int i = 0; i < kGroups; i++) {
+    uint64_t weight = 5;
+    if (i == 0)
+      weight = 2;
+    else if (i == (kGroups - 1))
+      weight = 1;
+    
+    const Vertex::Index next_hub = counter++;
+
+    for (int j = 0; j < (kNodesPerGroup - 1); j++) {
+      const Vertex::Index node = counter++;
+      graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight));
+      graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight));
+    }
+    last_hub = next_hub;
+  }
+  
+  graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5));
+  
+  
+  EXPECT_EQ(counter, graph.size());
+
+  CycleBreaker breaker;
+  
+  set<Edge> broken_edges;
+  LOG(INFO) << "If this hangs for more than 1 second, the test has failed.";
+  breaker.BreakCycles(graph, &broken_edges);
+  
+  set<Edge> expected_cuts;
+
+  for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(),
+       e = graph[n_root].out_edges.end(); it != e; ++it) {
+    expected_cuts.insert(make_pair(n_root, it->first));
+  }
+
+  EXPECT_TRUE(broken_edges == expected_cuts);
+}
+
 TEST(CycleBreakerTest, WeightTest) {
   int counter = 0;
   const Vertex::Index n_a = counter++;