I'm experimenting a bit with aptitude search terms and finally discovered how to do search on dependencies, which is:
aptitude search '?depends("searchterm")' The only problem that I've found is... that the "searchterm" uses expansions. If I use aptitude search '?depends("vim")' it will look for any packages that depends on a package that contains the word vim in the start, middle or end. Is there a way that I can match the exact package called vim and no other expansion?
The argument of ?depends, like any other directive, is a search pattern. The pattern "vim" is a regular expression that the package name must contain. To search for an exact package name, you need to anchor the regex: "^vim$".
aptitude search '?depends("^vim$")' aptitude search '?depends(^vim$)' aptitude search '~D^vim$' You can also use the ?exact-name directive, but for some reason, at least with aptitude 0.6.6, it's slower.
aptitude search '?depends(?exact-name(vim))' 
aptitude search '?depends("^vim$")'returns a smaller list than just searching for vim, but I haven't confirmed its doing exactly what you are asking.?narrow(filter, pattern)??narrow(?name(vim), ?depends(?name(vim)))