Comment 29 for bug 868188

One more comment (hope people are not getting bored of me). If you do want to go down the dependency route, you could have the recommend be the xz-lzma package rather than the lzma package. The difference being that xz-lzma does not include any new binaries itself but rather is a set of symlinks pointing to the xz binaries. Wereas the lzma package installs the older lzma utils, which are no longer actively maintained (note: the upstream maintainer of lzma utils is the same as xz utils. He considers xz to be the replacement for lzma, which is why it is backwards compatible in the first place).