// Consider other options
                        if (InOr == false)
                        {
-                          if (Debug == true)
-                             clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
-                          Cache.MarkDelete(I);
-                          if (Counter > 1)
+                          if (Cache.IsAutoInstallOk(I) == true)
                           {
-                             if (Scores[Pkg->ID] > Scores[I->ID])
-                                Scores[I->ID] = Scores[Pkg->ID];
-                          }                       
-                       }                       
+                             if (Debug == true)
+                                clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
+                             Cache.MarkDelete(I);
+                             if (Counter > 1)
+                             {
+                                if (Scores[Pkg->ID] > Scores[I->ID])
+                                   Scores[I->ID] = Scores[Pkg->ID];
+                             }
+                          } else {
+                             /* The dependency of the TargetPkg would be satisfiable with I but it is
+                                forbidden to install I automatical, so anything we can do is hold
+                                back the TargetPkg.
+                             */
+                             if (Debug == true)
+                                clog << "  Hold back " << Start.TargetPkg().Name() <<
+                                       " rather than change denied AutoInstall " << I.Name() << endl;
+                             Cache.MarkKeep(Start.TargetPkg());
+                          }
+                       }
                     }
                  }
                                  
 
    library can override this method to control the MarkInstall behaviour */
 bool pkgDepCache::IsAutoInstallOk(const PkgIterator &Pkg, unsigned long Depth)
 {
-   return true;
+   return (Pkg->SelectedState != pkgCache::State::Hold);
 }
                                                                        /*}}}*/
 // DepCache::SetReInstall - Set the reinstallation flag                        /*{{{*/
 
     adjustable
   * do not write state file in simulate mode (closes: #433007)
   * add hook for auto-install (closes: #470035)
+  * support IsAutoInstallOk in the resolver too
 
+  [ Michael Vogt ]
+  * honor the dpkg hold state in IsAutoInstallOk (closes: #64141)
+  
   [ Julian Andres Klode ]
   * apt-pkg/contrib/configuration.cc: Fix a small memory leak in
     ReadConfigFile.