Меня очень удивила подобная зависимость. С точки зрения пользователя пакета kcachegrind я не вижу разумного обоснования для её появления.

$ apt-cache showpkg kdesdk-kcachegrind
Package: kdesdk-kcachegrind
Versions: 
3.5.10-alt0.M41.1(/var/lib/apt/lists/_media_SPACE_branch_i586_base_pkglist.classic)

Reverse Depends: 
  kdesdk,kdesdk-kcachegrind 3.5.10-alt0.M41.1
Dependencies: 
3.5.10-alt0.M41.1 - kdelibs (2 3.5.10-alt0.M41.1) kdesdk-common (5 3.5.10-alt0.M41.1) valgrind (0 (null)) /bin/sh (0 (null)) /bin/sh (0 (null)) /lib/ld-linux.so.2 (0 (null)) /usr/bin/env (0 (null)) /usr/bin/perl (0 (null)) /usr/bin/php (0 (null)) /usr/bin/python (0 (null)) /usr/share/doc/HTML/en/common (0 (null)) libDCOP.so.4 (0 (null)) libc.so.6(GLIBC_2.0) (0 (null)) libc.so.6(GLIBC_2.1) (0 (null)) libc.so.6(GLIBC_2.1.3) (0 (null)) libc.so.6(GLIBC_2.4) (0 (null)) libgcc_s.so.1(GCC_3.0) (0 (null)) libgcc_s.so.1(GLIBC_2.0) (0 (null)) libkdecore.so.4(CXX3) (0 (null)) libkdeui.so.4 (0 (null)) libkio.so.4 (0 (null)) libm.so.6(GLIBC_2.0) (0 (null)) libpthread.so.0(GLIBC_2.0) (0 (null)) libqt-mt.so.3(CXX3) (0 (null)) libstdc++.so.6(CXXABI_1.3) (0 (null)) libstdc++.so.6(GLIBCXX_3.4) (0 (null)) perl(Config.pm) (0 (null)) perl(Getopt/Std.pm) (0 (null)) perl(IO/File.pm) (0 (null)) python2.5(encodings) (0 (null)) python2.5(hotshot) (0 (null)) python2.5(os) (0 (null)) rtld(GNU_HASH) (0 (null)) kcachegrind (0 (null)) 
Provides: 
3.5.10-alt0.M41.1 - kdesdk-kcachegrind kcachegrind 
Reverse Provides: 
kdesdk-kcachegrind 3.5.10-alt0.M41.1