diff --git a/cycle_breaker.cc b/cycle_breaker.cc
index 552a54f..266c2df 100644
--- a/cycle_breaker.cc
+++ b/cycle_breaker.cc
@@ -34,8 +34,16 @@
   // and looking for the strongly connected component with vertex s.
 
   TarjanAlgorithm tarjan;
+  skipped_ops_ = 0;
     
   for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
+    DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+    if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+      skipped_ops_++;
+      continue;
+    }
+
     if (i > 0) {
       // Erase node (i - 1) from subgraph_. First, erase what it points to
       subgraph_[i - 1].out_edges.clear();
@@ -71,6 +79,7 @@
   }
   
   out_cut_edges->swap(cut_edges_);
+  LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
   DCHECK(stack_.empty());
 }
 
@@ -116,7 +125,7 @@
 
 bool CycleBreaker::StackContainsCutEdge() const {
   for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
-        e = stack_.end(); it != e; ++it) {
+           e = stack_.end(); it != e; ++it) {
     Edge edge = make_pair(*(it - 1), *it);
     if (utils::SetContainsKey(cut_edges_, edge)) {
       return true;
diff --git a/cycle_breaker.h b/cycle_breaker.h
index 9c10c17..f1fa677 100644
--- a/cycle_breaker.h
+++ b/cycle_breaker.h
@@ -28,8 +28,11 @@
 
 class CycleBreaker {
  public:
+  CycleBreaker() : skipped_ops_(0) {}
   // out_cut_edges is replaced with the cut edges.
   void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
+  
+  size_t skipped_ops() const { return skipped_ops_; }
 
  private:
   void HandleCircuit();
@@ -44,6 +47,10 @@
   Graph blocked_graph_;  // "B" in the paper
 
   std::set<Edge> cut_edges_;
+  
+  // Number of operations skipped b/c we know they don't have any
+  // incoming edges.
+  size_t skipped_ops_;
 };
 
 }  // namespace chromeos_update_engine
diff --git a/cycle_breaker_unittest.cc b/cycle_breaker_unittest.cc
index d06fe81..9922917 100644
--- a/cycle_breaker_unittest.cc
+++ b/cycle_breaker_unittest.cc
@@ -20,6 +20,14 @@
 
 namespace chromeos_update_engine {
 
+namespace {
+void SetOpForNodes(Graph* graph) {
+  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+    it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  }
+}
+}  // namespace {}
+
 class CycleBreakerTest : public ::testing::Test {};
 
 TEST(CycleBreakerTest, SimpleTest) {
@@ -35,6 +43,7 @@
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
   graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
@@ -109,6 +118,7 @@
   const int kGroups = 33;
   
   Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
+  SetOpForNodes(&graph);
   
   const Vertex::Index n_root = counter++;
 
@@ -166,6 +176,7 @@
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4));
   graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3));
@@ -208,6 +219,7 @@
   const Graph::size_type kNodeCount = counter++;
 
   Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
 
   graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
   graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
@@ -226,4 +238,27 @@
   EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
 }
 
+TEST(CycleBreakerTest, SkipOpsTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+  graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
+
+  CycleBreaker breaker;
+  
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+  
+  EXPECT_EQ(2, breaker.skipped_ops());
+}
+
 }  // namespace chromeos_update_engine